[JAVA]백준 15989: 1,2,3 더하기 4

백준 15989: 1,2,3 더하기 4

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

풀이

첫번째 풀이

• 처음에는 단순히 조합으로 풀이했다.
• 1,2,3 중 원소를 중복으로 사용하며 조합으로 풀이
• 당연하게도 실패

두번째 풀이

• 1,2,3으로 각각 이루어진 원소들 + 2,3이 합쳐진 원소를 더해서 구했다.
• 비효율적이지만 어쨋든 정답
• 아래는 조합메서드와 두번째 풀이 코드

  import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

    public static void main(String[] args) throws  Exception{
        int T = Integer.parseInt(br.readLine());
        for(int t= 0;t<T;t++){
            int n = Integer.parseInt(br.readLine());
            int cnt = 1+n/2+n/3;
            for(int i =1;i<=n/2;i++){
                for(int j =1;j<=n/3;j++){
                    if(i*2+j*3<=n){
                        cnt++;
                    }else{
                        break;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }

    static int comb(int n, int sum, int cur){
        if(sum==n){
            return 1;
        }
        int cnt = 0;
        for(int i = cur;i<=3;i++){
            if(sum+i<=n){
                cnt+=comb(n,sum+i, i);
            }
        }
        return cnt;
    }

}

세번째 풀이

• 두번째 풀이로 정답이 나온 후, 내 코드가 너무 느리다는 것을 발견
• 다른 사람의 코드를 보니 dp로 푸는 문제였음.
• n번째 수를 1,2,3으로 나타내는 것을 오름차순 정렬했을 때의 경우의 수는 다음과 같다.
  • 1로 끝나는 경우
  • n-2의 1로 끝나는 경우 + n-2의 2로 끝나는 경우 -> 마지막에 2를 하나 추가할 수 있으니
  • n-3의 1로 끝나는 경우 + n-3의 2로 끝나는 경우, n-3의 3으로 끝나는 경우 -> 마지막에 3을 추가할 수 있으니
• 이렇게 계산하여 n번째수의 1,2,3으로 ㅅ끝나는 경우를 모두 더하면 된다.

package algorithm2024.sep.day13;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_15989_123_더하기_4 {

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

    public static void main(String[] args) throws  Exception{
        int T = Integer.parseInt(br.readLine());
        for(int t= 0;t<T;t++){
            int n = Integer.parseInt(br.readLine());
            int cnt = 0;
            int[][] dp = new int[10001][4];
            dp[1][1] = 1;
            dp[2][1] = 1;
            dp[2][2] = 1;
            dp[3][1] = 1;
            dp[3][2] = 1;
            dp[3][3] = 1;
            for(int i =4;i<=n;i++){
                dp[i][1] = 1;
                dp[i][2] = dp[i-2][1] + dp[i-2][2];
                dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
            }
            cnt = dp[n][1] + dp[n][2] + dp[n][3];
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }

}

---

Issue

• 문제를 풀어도 풀이에 확신이 없다면 정석 풀이를 보도록 하자.
• 비슷한 유형을 동일한 방법으로 풀었을 때 맞을 것이란 보장이 없다.