⚒️ Coding Test

[백준] 1, 2, 3 더하기 4 - 자바(Java)

dev-ong 2024. 8. 1. 09:06

문제 링크

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

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

  • 1+1+1+1
  • 2+1+1 (1+1+2, 1+2+1)
  • 2+2
  • 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

문제 풀이

[고려사항]

숫자 합은 중복이 없는 조합으로 구해야한다.

그리고 주어지는 테스트 케이스 개수는 최대 10,000개이므로 매 테스트마다 모든 수에 대한 계산을 하면 시간초과가 발생한다. 

[알고리즘, 구현방법]

이미 한 계산에 대한 값을 꺼내 쓰는 문제이기 때문에 DP 로 구현했다.

dp[i-1]은 dp[i]의 1을 포함한 숫자 합의 경우의 수이다.

dp[2]는 1+1, 2의 경우로 2가지의 합의 조합이 나온다.

dp[3]은 1+1+1, 1+2, 3 의 합의 조합이 나오는데, 이때 dp[2]의 (1+1)에 +1, 2에 +1을 한 두가지의 경우의 수가 무조건 포함된다

 

따라서 dp[i]는 dp[i-1]의 합의 조합에 +1을 한 경우와 2,3의 조합으로만 이루어진 합의 조합의 수를 합한 것이 된다.

dp[i] = dp[i-1] + (2,3으로만 이루어진 합의 조합)

 

2,3으로만 이루어진 합의 조합을 찾는 방법은 아래와 같다.

n을 2로 나눈 몫만큼 반복하면서, 2의 개수를 순차적으로 줄여, 2,3의 합으로 n을 만들 수 있다면 카운팅하면 된다.

예를 들어, n = 10 일때, 10을 2로 나눈 몫은 5이다. 2의 개수를 5개, 4개, 3개, 2개, 1개로 줄이면서 3과의 합의 조합이 되는지 확인한다.

  • 2가 5개: 10 - (2 * 5) = 0이므로 합이 된다. (O)
  • 2가 4개: 10 - (2 * 4) = 2 | 2 < 3이므로 합이 되지 않는다. (X)
  • 2가 3개: 10 - (2 * 3) = 4 | 4 > 3 | 4 % 3 != 0 이므로 합이 되지 않는다. (X) 
    • → 10에서 2를 3개 합한 6을 뺀 값인 4는 3보다 크지만 3으로 나누어떨어지지 않기 때문
  • 2가 2개: 10 -(2 * 2) = 6 | 6 > 3 | 6 % 3 = 0 이므로 합이 된다. (O)
  • 2가 1개: 10 -(2 * 1) = 8 | 8 > 3 | 8 % 3 != 0 이므로 합이 되지 않는다. (X)
  • 2가 0개: 10 -(2 * 0) = 10 | 10 > 3 | 10 % 3 != 0 이므로 합이 되지 않는다. (X)

 

정리하면,

n을 2로 나눈 몫부터 0까지, 2의 개수를 순차적으로 줄이면서 n과 2의 개수만큼의 합을 뺀 값이 0이거나, 3보다 크고 3으로 나누어떨어지는 경우에만 합이 되는 경우로 쳐서 dp[n]에 카운팅하면 된다.

[풀이 과정]

1. dp[] 정수 배열은 n의 최댓값 + 1로 초기화, dp[1] = 1로 할당

2. 테스트 케이스만큼 반복

3. 2부터 n까지 반복하면서 dp 값 계산

  • 이전에 이미 계산된 값은 넘어감
  • 2로 나눈 몫에서 0까지 반복하면서 2의 개수를 줄여가며 3과 합의 조합이 이루어지는지 확인
    • 현재 dp[i] 라 했을때, i가 2의 배수인 경우, 카운팅
    • i 에서 2의 개수의 합을 뺀 값이 3보다 크고(AND) 3으로 나누어 떨어지는 경우, 카운팅

4. dp[n] 출력

정답 코드

import java.io.*;

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());

        int[] test = new int[t];
        for (int i = 0; i < t; i++) {
            test[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[10001]; // n 은 최대 10,000
        dp[1] = 1;
        for (int num : test) { // Test case 만큼 반복
            for (int i = 2; i <= num; i++) {
                if (dp[i] > 0) continue; // 이미 계산된 값은 넘어감
                int count = 0;
                int div = i / 2;
                for (int j = div; j >= 0; j--) { // 2로 나눈 몫만큼 반복하면서 2의 개수를 순차적으로 줄임
                    int diff = i - (j * 2);
                    // i가 2의 배수인 경우(diff == 0)
                    // 2를 i개 만큼 더한 후 남은 수를 3으로 나누어서, 나누어 떨어지면 3을 채워서 합으로 만들 수 있는 경우
                    if (diff == 0 || (diff >= 3 && diff % 3 == 0)) count++;
                }
                dp[i] = dp[i-1] + count; // dp[i] = dp[i-1] + (2,3으로만 이루어진 합)
            }
            System.out.println(dp[num]);
        }
    }
}