[1일1커밋 9D] 백준 JAVA 14501, 13458, 14888

14501. 퇴사 (실버3) https://www.acmicpc.net/problem/14501

DP

나도 하고싶다 퇴사! 풀기 전 문제 유형 중에 브루트포스 보고 대충 빡구현 하기로 결심함

며칠을 혼자 반복문에 별 조건 다 써가면서 풀다가 이건 글렀다 싶어 구글링했다. 결국 DP가 답이었다. 나처럼 빡구현 시도한 사람은 없으려나

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static int[] tarr;
	static int[] parr;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n=Integer.parseInt(br.readLine());
		tarr = new int[n]; // 상담 기간  
		parr = new int[n]; // 금액 
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			tarr[i] = Integer.parseInt(st.nextToken());
			parr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[n+1];
		for(int i=0; i<n; i++) {
			if(i+tarr[i] <=n ) { 
				dp[i+tarr[i]] = Math.max(dp[i+tarr[i]], dp[i]+parr[i]); 
			}
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}
		
		System.out.println(dp[n]);
	}
}

• i일째 일을 했을 때 근무 기간(n)을 벗어나지 않는다면, 해당 일자(i+tarr[i]) 까지의 최대 금액을 구한다.
  dp 배열에서 해당 일자(i+tarr[i]) 근무 금액의 최대값을 구한다. 기존에 저장된 값과 i일 상담 근무를 했을 경우 금액(dp[i]+parr[i])을 비교한다.
• i+1일에 대해 매번 최대값을 갱신해준다.

아무래도 DP 공부좀 하고 다시 봐야할 듯.. TODO

참고한 블로그1) https://yeons4every.tistory.com/62

백준 14501 : 퇴사 _자바 Java

참고한 블로그2) https://velog.io/@byeble23/%EB%B0%B1%EC%A4%80-14501%EB%B2%88%ED%87%B4%EC%82%AC-Java-%EC%BD%94%EB%93%9C%EB%A6%AC%EB%B7%B0

[백준] 14501번(퇴사) - Java 코드리뷰

 

13458. 시험 감독 (브론즈2) https://www.acmicpc.net/problem/13458

수학

엄청 간단한 계산 문제인데 왜 자꾸 '틀렸습니다' 나오나 봤더니 int 형이 아니라 long 이였다. 에라이

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

import java.io.*;
import java.util.*;

public class Main {

	static long n; //시험장 수 
	static float[] a; //응시자 수 
	static float b, c; // 총감독관이 한 시험장에서 감시할 수 있는 응시자 수, 부감독관이 감시할 수 있는 응시자 수
	static long result=0;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		a = new float[(int) n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) a[i] = Float.parseFloat(st.nextToken());
		st = new StringTokenizer(br.readLine());
		b = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		result = n; // 총감독관
		for(int i=0; i<n; i++) {
			a[i] -= b; // 총감독관 감시 응시자수 제외
			if(a[i]>0) result += Math.ceil((float)(a[i]/c));
		}
		
		System.out.println(result);
		br.close();
	}
}

 

14888. 연산자 끼워넣기 (실버1) https://www.acmicpc.net/problem/14888

백트랙킹, DFS

완전탐색을 하고싶은데.. 딱히 방법이 안떠올라서 순열을 쓰나 뭘 하나 고민했다. DFS를 활용한 백트랙킹이라 한다. 못하는거 투성이

백트랙킹 알고리즘 https://velog.io/@gayeong39/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BackTracking

백트래킹 알고리즘 (BackTracking)

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static int[] a;
	static int[] ops = new int[4];
	static long min=Integer.MAX_VALUE, max=Integer.MIN_VALUE;
 	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) a[i]=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++) ops[i]=Integer.parseInt(st.nextToken());
		
		backTracking(a[0], 1);
		bw.write(max+"\n"+min);
		
		bw.flush();
		bw.close();
		br.close();
	}
 	
 	static void backTracking(int num, int idx) { // 현재 계산중인 숫자, 인덱스(숫자 배열 a) 
 		if(idx==n) {
 			min = Math.min(min, num);
 			max = Math.max(max, num);
 		}
 		
 		for(int i=0; i<4; i++) {
 			if(ops[i]>0) {
 				ops[i]--; // 연산자 사용 
 				switch(i) {
 				case 0: backTracking(num+a[idx], idx+1); break;
 				case 1: backTracking(num-a[idx], idx+1); break;
 				case 2: backTracking(num*a[idx], idx+1); break;
 				case 3: backTracking(num/a[idx], idx+1); break;
 				}
 				ops[i]++; // 재귀 호출 후 개수 원복 
 			}
 		}
 	}
}

• 연산자를 사용했음으로 해당 연산자의 수를 줄인다.
• 4개의 각 연산자를 활용해 계산한다. 이때 재귀로 호출
• 재귀가 끝나면 다시 연산자 수를 원복시켜준다.
• 계산에 사용되는 숫자의 순서는 정해져있음으로, idx를 사용해 하나씩 빼서 사용한다.
• 배열의 모든 숫자 사용이 끝나면, 즉 식이 끝나 값이 최종으로 나오면 idx==n 인 조건이 만족됨으로 그때 최댓값과 최솟값을 구한다.