공부 119일차: 백준 9095번 1, 2, 3 더하기 자바 java

9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

 

 

 

---

백준 9095번 문제 1, 2, 3 더하기

---

문제

---

 

 

 

---

과정 생각해보기 & 오답

---

 

 처음엔 직접 7이 44번 나온다는 걸 순서 구하는 공식으로 풀어보면서 직접 계산해냈는데(공통점 찾아보려고),

공식은 찾았지만 그 공식 전에 또 도출해야 하는 것이 있어서 완전 막혔다

 

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));
        
 
        /*
         * 숫자 조합 구하고
         * 배열 구하는 방식으로 처리
         * */
        
        int t = Integer.parseInt(br.readLine());
        int[] arr = {1, 2, 3};
        
        int count = 1;    //전체가 1인 경우 더하고 시작
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            
        }
    }
 
}
 

여기서 멈춤..

이후로 아침부터 고민해봤지만 답이 떠오르지 않음.. 무엇보다 저 공식으로는 처리 시간이 너무 오래 걸릴 것 같았다

 

https://url.kr/s7amnq

결국 참고한 블로그는 위의 주소

 

 

 

---

정답 인정 코드

---

 

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));
        
        int t = Integer.parseInt(br.readLine());
        int[] dp = new int[11];    // 인덱스 10이 있어야 하므로 11크기의 배열
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i = 4; i < 11; i++) {    // 구해진 1~3 이후부터 배열 채우기
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
 
}
 

 

주석에 설명을 적었다

 

 

---

첫 다이나믹 프로그래밍 문제는 이렇게..