[백준] 1, 2, 3 더하기 2 (!) (12101번 JAVA)

[백준]  1, 2, 3 더하기 2 (!) (12101번 JAVA)

---

[접근방법]

정수 n을 1,2,3의 합으로 나타내는 방법 중 사전 순으로 k 번째 오는 식을 구하는 프로그램을 작성해야 한다.

따라서, 식은 ArrayList 을 String 타입으로 선언하여 사용한다.

 

ArrayList<String> arr 로 선언 할때,

arr[ i - 1 ] 에 있는 수식에 "+ 1"을 붙여준다.

arr[ i - 2 ] 에 있는 수식에 "+ 2"을 붙여준다.

arr[ i - 3 ] 에 있는 수식에 "+ 3"을 붙여준다.

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        ArrayList<String>[] arr = new ArrayList[n + 3];

        // 배열 초기화
        for(int i=0; i<=n+2; i++){
            arr[i] = new ArrayList<>();
        }
        
        // 초기값 입력
        arr[1].add("1");
        arr[2].add("1+1");
        arr[2].add("2");
        arr[3].add("1+1+1");
        arr[3].add("1+2");
        arr[3].add("2+1");
        arr[3].add("3");

        for(int i=4; i<=n; i++){
        	/*
            arr[i-1]에 "+1"을,
            arr[i-2]에 "+2"를,
            arr[i-3]에 "+3"을 붙힘
            */
            for(int j=1; j<=3; j++){
                for(String s : arr[i - j]){
                    arr[i].add(s + "+" + j);
                }
            }
        }

		// k번째 수식이 존재하지 않으면 -1 출력
        if (arr[n].size() < k){
            bw.write(-1 + "\n");
        }
        // 존재한다면, 정렬 후 k 번째 수식 출력
        else {
            Collections.sort(arr[n]);
            bw.write(arr[n].get(k-1));
        }

        bw.flush();
        bw.close();
    }
}

 

 

** for문의 활용

향상된 for문 : 배열이나 컬렉션에 저장된 값을 매 반복마다 하나씩 읽어와서 값에 저장한다.

int[] arr = {1, 2, 3, 4, 5, 6, 7};

for(int i : arr){
	System.out.println(i);
}

/*
1
2
3
4
5
6
7
*/

---

[2회차 풀이]

[접근 방법]

1회차 풀이와 같다.

 

실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N < 11)
k의 범위 (1<= k <= 2^31 -1)
O(N^2) = 11 * 11 = 121 (가능)

=> 별도의 시간 복잡도 고려 X

 

[JAVA 코드]

// 12101 - 1, 2, 3 더하기 2
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        ArrayList<String>[] arr = new ArrayList[n+3];

        // 배열 속 문자열을 생성 (초기화) - null 값을 제거
        for(int i=0; i<=n+2; i++){
            arr[i] = new ArrayList<>();
        }

        arr[1].add("1");
        arr[2].add("1+1");
        arr[2].add("2");
        arr[3].add("1+1+1");
        arr[3].add("1+2");
        arr[3].add("2+1");
        arr[3].add("3");

        // 1. DP 방식을 사용하여 arr[n] 수식 구하기
        for(int i=4; i<=n; i++){
            /*
             * arr[i-1]의 수식들은 "+1"을 하여, arr[i]에 저장
             * arr[i-2]의 수식들은 "+2"을 하여, arr[i]에 저장
             * arr[i-3]의 수식들은 "+3"을 하여, arr[i]에 저장
            */
            for(int j=1; j<=3; j++){
                for(String s : arr[i-j]){
                    arr[i].add(s + "+" + j);
                }
            }
        }

        // 2. 출력
        // k번째 수식이 없는 경우
        if (k > arr[n].size()){
            bw.write(-1+"\n");
        }
        else{ // n을 이루는 k번째 수식 출력
            Collections.sort(arr[n]);
            bw.write(arr[n].get(k-1) + "\n");
        }

        bw.flush();
        
        bw.close();
        br.close();
    }
}


/*
실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N < 11)
k의 범위 (1<= k <= 2^31 -1)
O(N^2) = 11 * 11 = 121 (가능)

=> 별도의 시간 복잡도 고려 X
*/

 

[Rewind]

1. 어려웠던 점

-  DP를 이용한 해결방안이 떠오르지 않았다.

-  ArrayList를 사용한 해결방안이 떠오르지 않았다.

★ ArrayList 배열의 크기를 "n+3"으로 하는 이유를 알지 못하겠다.

(n+1로 해도 충분할 것 같은데 ArrayOutOfBounds가 발생한다.)

- ArrayList 배열을 사용할때, 각 인덱스에 위치한 ArrayList 들을 초기화 해주어야 null 값을 다루는 오류가 발생하지 않는다.

 

2. 알게된 점
- ArrayList의 배열을 초기화 하지 않는 경우,

위와 같은 오류가 발생한다. 

 

java.lang.NullPointerException이 발생되는 가장 큰 원인은 Java 프로그래밍에서 사용할 객체를 생성한 후에 인스턴스를 생성하지 않은 상태에서 Null 오브젝트를 사용하려고 할 때에 발생한다.

 

이를 방지 하기 위해 사용 전 ArrayList 를 초기화 해야한다.

 

3. 개선 방안

★ ArrayList 배열의 크기를 "n+3"으로 하는 이유을 고민 해야 한다.