[BOJ] 9095 - 1, 2, 3 더하기 Java 풀이

풀이

문제 링크는 아래에 있다.

BOJ 9095 - 1, 2, 3 더하기

처음 생각했던 풀이는 다음과 같다.

어떤 수는 n이 있다고 할 때, 그 n을 만드는 방법은 세 가지가 있다.

n을 만드는 방법 = n - 1 에 1을 더하기 + n - 2에 2를 더하기 + n - 3 에 3을 더하기

이 말은 다음과 같다고도 볼 수 있다.

n을 만드는 방법의 수 = n - 1을 만드는 방법의 수 + n - 2를 만드는 방법의 수 + n - 3을 만드는 방법의 수

왜냐하면 n - 1 에서 n을 만드는 방법은 + 1 을 하는 한가지 방법 밖에 없기 때문이다.
마찬가가지로 n - 2에서 n을 만드는 방법도 한가지이며, n - 3에서 n을 만드는 방법도 한가지 뿐이다.
따라서 우리는 n을 만드는 방법의 수를 memoization[n]에 저장한다고 하면 다음과 같이 쓸 수 있다.

memoization[n] = memoization[n -1] + memoization[n - 2] + memoization[n -3]

이를 바탕으로 문제를 해결하였다.

구현

코드는 다음과 같다

import java.util.*;

class Solution {
    private final int[] input;
    private final int[] memoization;
    Solution(int[] input) {
        this.input = input;
        this.memoization = new int[11];
        memoization[1] = 1;
        memoization[2] = 2;
        memoization[3] = 4;
    }

    public String getAnswer() {
        StringBuilder builder = new StringBuilder();
        for(int i = 4; i <= 10; i++) {
            memoization[i] = memoization[i - 3] + memoization[i - 2] + memoization[i - 1];
        }
        for(int i = 0; i < input.length; i++)
            builder.append(memoization[input[i]] + "\n");
        return builder.toString();
    }

}


class Main {
  public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      int numOfTest = scanner.nextInt();
      int[] input = new int[numOfTest];
      for(int i = 0; i < numOfTest; i++) {
          input[i] = scanner.nextInt();
      }
      System.out.println(new Solution(input).getAnswer());
  }
}

memoization배열에 부분문제의 답을 저장하는 식으로 문제를 해결하였다.
memoization[n - 3] + memoization[n - 2] + memoization[n - 1] 이기 때문에, memoization[3] 까지는 수를 구해서 직접 넣었다.

그 후에 for 문을 돌려서 해결하였다.