Do it! 알고리즘 코딩 테스트(85번 ~ 86번)

85번 퇴사

---

내가 떠올린 풀이 해설

max[i] : i번째 날부터 퇴사날까지 벌 수 있는 최대 수입

max[i] = max[i] + 1  : 오늘 시작되는 상담을 했을 때 퇴사일까지 끝나지 않는 경우

max[i] = Math.max(max[i + 1], max[i + day[i]] + pl[i]) : 오늘 시작되는 상담을 했을 때 퇴사일 안에 끝나는 경우

if(i + day[i] > n + 1) : i번째 상담을 퇴사일까지 끝낼 수 없을 때

---

정확한 풀이

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

public class Baek14501 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] max = new int[n + 2];
		int[] day = new int[n + 1];
		int[] pl = new int[n + 1];
		
		for(int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			day[i] = Integer.parseInt(st.nextToken());
			pl[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = n; i > 0; i--) {
			if(i + day[i] > n + 1) {
				max[i] = max[i + 1];
			}
			else {
				max[i] = Math.max(max[i + 1], pl[i] + max[i + day[i]]);
			}
		}
		System.out.println(max[1]);
	}
}

---

86번 이친수

---

내가 떠올린 풀이 해설

d[i][0] : i 길이에서 끝이 0으로 끝나는 이친수의 개수 = d[i - 1][1] + d[i - 1][0];

d[i][1] : i 길이에서 끝이 1로 끝나는 이친수의 개수 = d[i - 1][0];

---

정확한 풀이

package DoitCodingTest;
import java.io.*;
import java.util.*;
public class Baek2193 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[][] d = new long[n + 1][2];
		d[1][1] = 1;
		d[1][0] = 0;
		for(int i = 2; i <= n; i++) {
			d[i][0] = d[i - 1][1] + d[i - 1][0];
			d[i][1] = d[i - 1][0];
		}
		System.out.println(d[n][0] + d[n][1]);
	}

}

---

오늘의 회고

DP에서 점화식을 잘 못세우겠습니다. 아직 많이 부족하고 많은 연습이 필요할 것 같습니다. 포기하지 않고 끝까지 최선을 다해보겠습니다.