[Java][백준 골드 5] 1,2,3 더하기 4 - 1

1) 문제 정보

• 문제명: 1,2,3 더하기 4
• 번호: 15989
• 플랫폼: 백준
• 링크: https://www.acmicpc.net/problem/15989
• 난이도: 골드 5
• 유형: DP

2) 문제 요약

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다.
단, 순서만 다른 식은 같은 경우로 본다.

 

3) 내 풀이 아이디어

내 코드는 3을 몇 개 쓰는지 먼저 고정한 뒤, 나머지를 1과 2로 채우는 방식이다.

• 3을 j개 쓰면 남은 값은 n - 3j
• 남은 값을 1,2로 만드는 경우의 수는 남은값 / 2 + 1
• j=0부터 j=n/3까지 전부 더하면 정답

순서를 직접 만들지 않고 조합 개수만 세기 때문에 중복 처리가 자연스럽다.

 

 

4) 풀이 방법

1. 테스트케이스 수 입력
2. 각 n에 대해 결과값 초기화
3. j를 증가시키며 경우의 수 누적
4. 결과 출력
   • 시간복잡도: O(n/3) (테스트케이스당)
   • 공간복잡도: O(1)

 

 

5) 내 코드

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());


        for(int i = 0; i < n; i++){
            int a = Integer.parseInt(br.readLine());
             int result = 1;
             result += a/2;
             for(int j = 1; j <= a/3; j++){
                 int a1 = a-3*j;
                 result += a1/2+1;
             }
             sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

6) 코드 해설

• result = 1 + a/2: 3을 사용하지 않는 경우를 먼저 반영
• for (j = 1; j <= a/3; j++): 3을 쓰는 경우를 순회
• a1 = a - 3*j: 3을 뺀 나머지
• result += a1/2 + 1: 나머지를 1,2로 만드는 조합 수 누적
• 7) 회고
• 이번에는 3의 개수를 고정하는 조합 카운팅 방식으로 풀어서 구현이 간단했다.
• 이 문제는 DP로도 정석적으로 풀 수 있다.
  dp[i][k] = i를 1~k만 사용해서 만드는 방법 수로 두면:
  • dp[i][1] = 1
  • dp[i][2] = dp[i][1] + dp[i-2][2] (i>=2)
  • dp[i][3] = dp[i][2] + dp[i-3][3] (i>=3)
• 최종 답은 dp[n][3].
• 다음에는 DP 테이블 방식으로도 구현해서 점화식 관점까지 같이 연습해보면 좋다.

 

 

7) 회고

• 이번에는 3의 개수를 고정하는 조합 카운팅 방식으로 풀어서 구현이 간단했다.
• 이 문제는 DP로도 정석적으로 풀 수 있다.
  dp[i][k] = i를 1~k만 사용해서 만드는 방법 수로 두면:
  • dp[i][1] = 1
  • dp[i][2] = dp[i][1] + dp[i-2][2] (i>=2)
  • dp[i][3] = dp[i][2] + dp[i-3][3] (i>=3)
• 최종 답은 dp[n][3].
• 다음에는 DP 테이블 방식으로도 구현해서 점화식 관점까지 같이 연습해보면 좋다.