[TIL] 99클럽 코테 스터디 29일차 TIL + 백준 9461 파도반 수열

문제 풀이

 

문제 탐색하기

수열의 규칙을 살펴보면 첫번째, 두번째, 세번째는 다 1이고 그 뒤로부터는 자신보다 3번째 앞에 있는 수와 2번째 앞에 있는 수를 더한 값임을 알 수 있습니다. 

 

따라서 DP 알고리즘을 활용하여 재귀함수로 이 문제를 풀 수 있습니다.

DP 알고리즘에 대해서는 아래 게시글에 작성해두었습니다.

https://coding-babo.tistory.com/173

[TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열

 

 

우선 N은 최대 100까지 주어질 수 있으므로 dp배열을 new long[101]로 선언합니다.

private static long wave(int N){
        if(waveArr[N] == 0L){
            waveArr[N] = wave(N-3) + wave(N-2);
        }
        return waveArr[N];
    }

 

dp 배열의 원소는 재귀호출을 이용하여 위와 같이 작성하면 dp배열의 원소값이 아직 구해지지 않았을 경우 값을 저장해줄 수 있습니다.

 

문제 풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static long[] waveArr = new long[101];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        waveArr[0] = 0L;
        waveArr[1] = 1L;
        waveArr[2] = 1L;
        waveArr[3] = 1L;

        int T = sc.nextInt();

        while(T-- > 0){
            System.out.println(wave(sc.nextInt()));
        }
    }

    private static long wave(int N){
        if(waveArr[N] == 0L){
            waveArr[N] = wave(N-3) + wave(N-2);
        }
        return waveArr[N];
    }

}

 

 

오늘의 회고

재귀함수를 사용해서 로직을 작성하는 것은 역시나,, 넘 어렵네여..