[백준] 9461번 파도반 수열 JAVA (자바) 풀이

문제 9461번 (DP)

 

: 첫 삼각형은 정삼각형으로 변의 길이는 1

  다음과 같은 과정으로 정삼각형을 계속 추가한다

  가장 긴 변의 길이를 k라 할 때, 변 길이가 k인 정삼각형을 추가

  파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이

  P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

  P(N)을 구하는 프로그램을 작성하시오

 

 

[입력]

 :  첫째 줄에 테스트 케이스의 개수 T

    각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다 (1 ≤ N ≤ 100)

 

 

[출력]

 :  각 테스트 케이스마다 P(N)을 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

 

1. 규칙 찾기

• 삼각형 그림을 보면 맞닿은 삼각형의 합이 다음 삼각형이 된다 
• 변의 길이 7+2 = 변의길이 9인 삼각형 생성
  변의 길이 5+2 = 변의길이 7인 삼각형 생성
  종합해서 보면 N-1번째 삼각형 N-5 번째 삼각형의 합은 N번째 삼각형의 길이와 같다
  
  

2. 수행이 안된다면 자료형 바꾸기

• int형에서 long으로 바꾸니 알맞게 돌아간다

 

 

 [코드]

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));
        int T = Integer.parseInt(br.readLine());
        long dp[] = new long[101];
        dp[1]=1;
        dp[2]=1;
        dp[3]=1;
        dp[4]=2;
        dp[5]=2;
        dp[6]=3;
        dp[7]=4;
        dp[8]=5;
        dp[9]=7;
        dp[10]=9;
        
        while(T-->0){
            int N = Integer.parseInt(br.readLine());
            for(int i=11; i<=N; i++){
                dp[i] = dp[i-1]+dp[i-5];
            }
            System.out.println(dp[N]);
            
        }
        
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    long dp[] = new long[101];  dp를 Long 타입으로 변경
   

 :  dp[1]=1;
    dp[2]=1;
    dp[3]=1;
    dp[4]=2;
    dp[5]=2;
    dp[6]=3;
    dp[7]=4;
    dp[8]=5;
    dp[9]=7;
    dp[10]=9;
        
 :  while(T-->0){
            int N = Integer.parseInt(br.readLine());
            for(int i=11; i<=N; i++){
                dp[i] = dp[i-1]+dp[i-5];  규칙에 맞춰 dp식 대입 
            }
            System.out.println(dp[N]);  결과 출력
    }
        
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *