[DP 연습] BOJ_15990 1, 2, 3 더하기 5 (S2)

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

제대로 돌아가지도 않는 내 코드와, 제대로 돌아가는 구글링 코드 순서!

 

그냥 DP는 거의 내가 직접 푼다기 보다는 솔루션을 보고 이해하면서 멱살잡혀 끌려가는 느낌이라서 속상하다. 이렇게 문제를 하나하나 채우고 랭킹을 올리고 티어를 올리는게 무슨 소용이 있는가 싶고, 이게 알고리즘 공부인가 싶다가도 그냥 이렇게라도 DP를 체험하다보면 체득이 되지 않을까 하는 생각에 솔루션을 보고 이해라도 하자.. 이렇게 된다. 

 

https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-15990-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-5-Java 이분 솔루션을 보고 이해하려고 노력했다. 여기서 얻어가야 할 아이디어는, dp[i][j] 에서 i와 j가 무엇을 의미하는지인데, 예를 들어 dp[7][3]의 의미는 7을 만드는 수식에서 3로 끝나는 경우에 해당한다는 것이다. 같은 수를 연달아서 쓰면 안되는 조건 때문에 2차원 배열을 사용한 것 같고, 특히 끝나는 경우들을 고려해준 것 같다.

 

DP의 핵심이 메모이제이션이라는 것은 알지만, 메모를 하는 자료구조를 어떤것을 선택할지가 중요할 것 같은데, 그게 잘 생각이 안떠오르는 것 같다.. 너무 어렵다진짜!

 

package algo0923;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 1,2,3 더하기 5
public class BOJ_15990 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			
			int N = Integer.parseInt(br.readLine());
			int[] dp = new int[N+1];
			
			dp[0] = 0; // 0
			dp[1] = 1; // 1
			dp[2] = 1; // 2
			
			for (int i = 3; i <= N; i++) {
				if (i%2==0) {
					dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]-1)%1000000009;
				}
				else {
					dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]+1)%1000000009;
				}
			}
			// 3 = 1+2 2+1 3+0 = 1 + 1 + 0 = 3
			// 4 = 3+1 2+2 1+3 = 3 + 2 + 1
			sb.append(dp[N]).append("\n");
		}
		System.out.println(sb.toString());
	}
}

package algo0923;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 1,2,3 더하기 5
// https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-15990-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-5-Java
// https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-12101-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-3-Java
public class BOJ_15990_sol {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());
		int size = 100000;
		int mod = 1000000009;

		// dp 배열 선언
		long[][] dp = new long[size + 1][4];

		// dp 기저조건 선언
		dp[1][1] = 1; // 1
		dp[2][2] = 1; // 2
		dp[3][3] = 1; // 3

		dp[3][1] = 1; // 1 + 2
		dp[3][2] = 1; // 2 + 1

		// dp 점화식
		for (int i = 4; i <= size; i++) {
			dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
			dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % mod;
			dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % mod;
		}

		// 테스트케이스 출력
		for (int i = 1; i <= T; i++) {
			int N = Integer.parseInt(br.readLine());
			sb.append((dp[N][1] + dp[N][2] + dp[N][3]) % mod).append("\n");
		}
		System.out.println(sb.toString());
	}
}