1, 2, 3 더하기(9095)

1, 2, 3 더하기(9095)

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();

    int t =  Integer.parseInt(br.readLine());
    for(int i = 0; i < t; i++) {
      int n = Integer.parseInt(br.readLine());
      sb.append(count(n)).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int count(int n) {
    
    if(n == 0) return 1;
  
    int cnt = 0;
    
    if(n >= 3) {
      cnt += count(n-3);
    }
    
    if(n >= 2) {
      cnt += count(n-2);
    }
    
    if(n >= 1) {
      cnt += count(n-1);
    }
    
    return cnt;
  }
}

풀이과정

1. 처음에는 증가되는 양을 체크하고 규칙을 찾으려고 했었다.
2. 1을 만드는 경우 1 , 2를 만드는 경우 2, 3은 4, 4는 7, 5는 13, 6은 23…
3. 여기서 실수는 수기로 경우를 찾아보았을 때 6이 나오는 경우의수를 23으로 했다
4. 그래서 각 수의 증가 폭에 대한 규칙을 정의 내릴 수가 없어서 재귀함수로 풀기로 하였다.
5. 반전… 재귀함수를 풀어보고 내가 찾은 수의 경우의 수가 잘 나오는지 대입해보다가 6을 넣으니 24개로 나왔다…

- 성공
- 메모리 : 14236 KB
- 시간 : 120 ms

• 다른 풀이
  1. 재귀함수로도 답은 나왔지만 증가폭의 규칙을 찾아보니
  2. 타켓의 이전 수 3개의 경우의 수들을 합한 것이었다.
  3. 4는 4+2+1 = 7 , 5는 7+4+2 = 13 , 6은 13+7+4 = 24 …

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();

    int t =  Integer.parseInt(br.readLine());
    
    int[] num = new int[11];
    num[1] = 1;
    num[2] = 2;
    num[3] = 4;

    for(int i = 4; i <= 10; i++) {
      num[i] = num[i-3] + num[i-2] + num[i-1];
    }
    
    for(int i = 0; i < t; i++) {
      int n = Integer.parseInt(br.readLine());
      
      sb.append(num[n]).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

- 성공
- 메모리 : 14116 KB
- 시간 : 120 ms

보안점

1. 생각보다 시간이 많이 걸렸는데,
2. 이유는 각 수의 증가폭에 대한 규칙을 찾으려고 했다.
3. 결론적으로 나쁜 접근은 아니었는데, 경우의 수를 수기로 찾는 과정에서 실수를 해버렸다.
4. 문제 풀이에 필요한 경우의 수들을 구할 때 좀 더 꼼꼼히 체크하여야겠다.