[java][boj][s3] 9095. 1, 2, 3 더하기

9095번: 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

/*
 * 입력
 * 1. 테스트 케이스 T
 * 2. 정수 n
 * 출력
 * 1. n을 1,2,3의 합으로 나타내는 방법의 수
 * 
 * >> 순서까지 따져야 함
 * >> 1 2 4 7 13 24 44
 * >> n = n-1 + n-2 + n-3
 */

분명 스터디원들과 dfs부터 천천히 복습하기로 하고 푼 문제였는데 어쩌다 보니 DP로 풀게 됐다... 아무리 봐도 dfs 각이 안 보여서 피보나치수열 문제를 풀때마냥 노가다로 숫자 적어서 계산했더니 예전에 풀었던 파도반수열과 같은 식이 나왔다 그때는 arr[n] = arr[n-2] + arr[n-3] = arr[n-1] + arr[n-5]였는데 이번에는 세 수를 더해야 값이 나와서 규칙을 찾는 데 애를 썼다

우선 N값이 1일 때부터 계산을 했을 때 1 2 4 7 13 24 44 의 수열이 나온다 이를 바탕으로 규칙을 찾으면 arr[n] = arr[n-1] + arr[n-2] + arr[n-3]라는 규칙이 나오게 된다 이 규칙을 바탕으로 코드를 짰다

 

초반 1, 2, 3에서 배열을 벗어나는 수가 생겨서 하나하나 예외 상황을 체크해 줬는데 스터디원의 코드를 보니까 처음부터 문제에 나온 대로 배열을 arr[11]로 정의하는 게 훨씬 나은 것 같다

 

dfs로 푼 코드도 봤는데 훨씬 깔끔했다 다음에 다시 해 봐야지

코드

package A형대비;

import java.io.*;
import java.util.*;

public class s3_9095_123더하기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc<=T; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			
			if(N == 1) {
				sb.append(1).append("\n");
				continue;
			}
			
			arr[0] = 1;
			
			if(N == 2) {
				sb.append(2).append("\n");
				continue;
			}
			
			arr[1] = 2;
			
			if(N == 3) {
				sb.append(4).append("\n");
				continue;
			}
			
			arr[2] = 4;
			
			for(int i = 3; i<N; i++) {
				arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
			}
			
			sb.append(arr[N-1]).append("\n");
			
		}
		
		System.out.println(sb);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘