[JAVA] 9095번 - 1, 2, 3 더하기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

dp문제라서 고정적인 값은 미리 배열에 넣어야한다!

이 문제 같은 경우 1은 1 /  2는 1+1, 2 / 3은 1+1+1, 1+2, 2+1 이렇게 3가지는 고정이다. 

그래서 고정적으로 배열에 먼저 넣는다. 

4는 이렇게 된다

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

그런데 가만 보면 

빨간색부분은 dp[3]에 포함된 경우의 수다.

파란색부분은 dp[2]에 포함된 경우의 수다.

초록색부분은 dp[1]에 포함된 경우의 수다.

각 경우의 수에 1,2,3만 나중에 더해주면 되니까 전체 경우의수는 변함이 없다!

결국 4+2+1 = 7 이 답이다. 일반화하

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

 

시간복잡도

O(N)이다 O(11) 로 시간내에 충분히 가능하다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. dp배열을 만들고 미리 값을 넣는다

2. 4부터 반복문을 수행하여 배열을 채운다

3. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

 

dp문제는 아직 어렵다 ㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int dp[] = new int[11];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
        
        int T = Integer.parseInt(br.readLine()); 
        
        int n =0;
        
        for(int t=0; t<T; t++) {
        	n = Integer.parseInt(br.readLine());
       
        	
        	dp[0] = 0;
        	dp[1] = 1;
        	dp[2] = 2;
        	dp[3] = 4;
        	
        	for(int i=4; i<=n; i++) {
        		dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        	}
        	System.out.println(dp[n]);
        }
        
       
        
    }
	    
   
	
}