자바 - 백준 12101 / 1, 2, 3 더하기 2

 

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

12101번: 1, 2, 3 더하기 2

실버1

 

구현 방법

n은 양수이며 11보다 작고, k는 2^31-1보다 작거나 같은 자연수라서 이중 포문 써도 된다.

 

1. n까지 가지는 총 갯수를 저장하는 배열 만들기 

2. 2차원 dp를 만들어서 숫자별로 합을 나타낼 수 있는 경우들 배열에 저장하기

3. bottom-up 방식의 점화식을 이용해서 원하는 값까지 저장하기

4. 사전순으로 정렬하기

 

코드

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

/**
 * 백준 12101
 * 1, 2, 3 더하기 2
 * 실버1
 * https://www.acmicpc.net/problem/12101
 */
public class Boj12101 {

    //내풀이
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        if (n == 1 && k == 1) {
            System.out.println("1");
            return;
        }

        if (n == 2 && k == 1) {
            System.out.println("1+1");
            return;
        }

        if (n == 2 && k == 2) {
            System.out.println("2");
            return;
        }

        if (n < 3 && k > 1) {
            System.out.println("-1");
            return;
        }

        int[] cnt = new int[n + 1];

        cnt[1] = 1;
        cnt[2] = 2;
        cnt[3] = 4;

        for(int i = 4; i < n+1; i++) {
            cnt[i] = cnt[i -1] + cnt[i - 2] + cnt[i - 3];
        }

        String[][] dp = new String[n + 1][cnt[n]];

        dp[1][0] = "1";

        dp[2][0] = "1+1";
        dp[2][1] = "2";

        dp[3][0] = "1+1+1";
        dp[3][1] = "1+2";
        dp[3][2] = "2+1";
        dp[3][3] = "3";

        for(int i = 4; i < n+1; i++) {

            for (int j = 0; j < cnt[i-3]; j++) {
                dp[i][j] = dp[i-3][j] + "+3";
            }

            for (int j = 0; j < cnt[i-2]; j++) {
                dp[i][cnt[i-3] + j] = dp[i-2][j] + "+2";
            }

            for (int j = 0; j < cnt[i - 1]; j++) {
                dp[i][cnt[i-3] + cnt[i -2] + j] = dp[i-1][j] + "+1";
            }
        }

        Arrays.sort(dp[n]);


        if(k > cnt[n]) {
            System.out.println(-1);
        } else {
            System.out.println(dp[n][k-1]);
        }
    }
}

느낀 점

배열로 받아서 구현했더니, 배열 인덱스 초과 오류 엄청 많이 떠서 예외사항을 앞에 많이 적었다.

리스트 형태로 받아서 구현 하는 걸로 고치면 코드가 깔끔해질거 같다.

구현 방법을 이해하기 쉽게 적는 연습이 필요. 

 

참고 블로그(1,2,3 더하기 시리즈 문제 잘 정리되어 있음)

https://velog.io/@jkh9615/series/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-%EC%8B%9C%EB%A6%AC%EC%A6%88

시리즈 | [알고리즘] 1, 2, 3 더하기 시리즈 - 방방다망함 (방방 싫어하는거 아님)