[Baekjoon/JAVA] 15989 1, 2, 3 더하기 4

 

 

문제가 짧아서 골랐는데 읽다보니 dp 의 느낌이 강해서 아 괜히 건드렸나 ........생각했던 문제 

근데 생각보다 규칙만 찾으면 쉽게 풀리는 문제였다

 

N = 1

1

 

N = 2

1 ( x 2)

2

 

N = 3

1 ( x 3)

2 ( + 1)

3

 

N = 4

1 ( x 4)

2 ( + 1) ( + 1)

3 ( + 1)

2 + 2

 

N = 5

1 ( x 5)

2 ( + 1) ( + 1)

3 ( + 1) ( + 1)

2 + 2 ( + 1)

3 + 2

 

N = 6

1 ( x 6)

2 ( + 1) ( + 1) ( + 1)

3 ( + 1) ( + 1) ( + 1)

2 + 2 ( + 1) ( + 1)

3 + 2 ( + 1)

2 + 2 + 2 

3 + 3

 

이런식으로 규칙을 보다보면, N-1 에서 N 으로 갈때 몇가지 케이스만 추가되는 것을 알 수 있다.

단순히 + 1을 하는 것은 경우의 수에 추가되지 않음을 알 수 있음.

 

1. 3 또는 3과 2로 이루어진 case 추가

        => 짝수일때는 3이 짝수개만 들어갈 수 있고, 홀수일 땐 홀수개만 들어갈 수 있음

 

2. 오로지 2만 있는 case 추가

         => N 이 짝수일 때만 가능

 

이전 값에 추가되는 case 의 개수만 더해주면서 정답을 구하면 되는 문제였다.

 

 

 

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int tc=0; tc<T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[] dp = new int[N+1];
            dp[1] = 1;
            for (int i=2; i<N+1; i++) {
                int divideTo3 = i / 3; // 3으로 나눴을 때 몫
                int additionalVal = 0; // 이전 숫자에서 더해야 할 값

                // 짝수라면
                if (i % 2 == 0) {
                    // 모두 2로 이루어진 case 추가
                    additionalVal += 1; 

                // 홀수라면
                } else {
                    // 3으로 나눴을 때 몫이 홀수라면
                    if (divideTo3 % 2 == 1) {
                        // 홀수가 하나 더 많으므로 1 추가
                        additionalVal += 1;
                    }
                }
                // 3 또는 3과 2로 이루어진 case 추가
                int temp = divideTo3 / 2;
                additionalVal += temp;
                dp[i] = dp[i-1] + additionalVal;
            }
            System.out.println(dp[N]);
        }
    }
}