[백준] 9095 : 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

수가 11밖에 없길래 배열을 생각했음

법칙이 있어서 단순하게 풂

1로만 이루어졌을 때, 2와 1로만 이루어졌을 때, 3이 포함됐을 때를 나눠서 코드를 구현해보자

 

내 코드

메모리 : 14120 KB

시간 : 128 ms

코드길이 : 632 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		int[] arr = new int[12];
		arr[1] = 1;
		arr[2] = 2;
		arr[3] = 4;
		for(int i = 4; i < 12; i++) {
			arr[i] = arr[i - 3] + arr[i - 2] +arr[i - 1];
		}
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			
			sb.append(arr[N]).append('\n');
		}
		System.out.print(sb);
	}
}

 

1등 코드

메모리 : 12860 KB

시간 : 64 ms

코드길이 : 542 B

 

[상위권 코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int total = Integer.parseInt(br.readLine());
		int[] ans = new int[total];
		int max=0;
		for(int c=0;c<total;c++){
			ans[c] = Integer.parseInt(br.readLine());
			if(max<ans[c]){
				max = ans[c];
			}
		}
		int[] arr = new int[max+1];
		arr[1]=1;
		arr[2]=2;
		arr[3]=4;
		for(int i=4;i<=max;i++){
			arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
		}
		for(int c=0;c<total;c++){
			System.out.println(arr[ans[c]]);
		}
	}

}