[Algorithm] 백준/Silver/9461. 파도반 수열 (반복문, 재귀함수)

하루입니다.

 

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

9461번: 파도반 수열

 

---

 

오늘의 문제는 파도반 수열. 이름이 예쁘다.

실버 3짜리 문제지만, ssafy 준비할 때 풀었던 기억이 있어서 도전했다.

 

 

 

문제점 : 아무리 봐도 내 점화식이 맞는데 자꾸 틀렸다고 함. 디버깅 돌렸는데도 도대체 틀린 게 뭔지 모르겠음. 질문게시판 찾아감. 보통 1. 배열 크기 잘못 설정 2. 값이 잘못 들어감 두 가지 원인 때문이었음. 나는 점화식이 맞으니까 값이 틀릴 리 없겠지! 라는 생각을 했는데, 사실 점화식 문제가 아닌 데이터타입 문제였음. 일정 숫자가 넘어가면 int의 범위를 넘어서 오버플로우가 발생하고, 값이 -로 변경되며 이상한 값을 출력하게 되어서 그런 거였다.

 

오버플로우가 되었는데 -가 되는 이유 : 자바의 int 타입은 4바이트의 크기를 가지며, 부호 비트를 포함하여 최대 2^31 - 1까지의 값을 표현할 수 있습니다. 따라서 int 변수에 저장된 값이 이 범위를 초과하면 오버플로우(overflow)가 발생합니다.

예를 들어, int 타입의 최대값인 2^31 - 1을 가지는 변수에 1을 더하면, 값은 -2^31이 됩니다. 이는 부호 비트가 1이 되면서 양수에서 음수로 바뀌고, 나머지 비트들이 0에서 1로 바뀌기 때문입니다.

 

 

고민의 흔적

 

 

해결 : 배열을 long으로 선언 후 사용했음.

 

의문 : 이런 문제는 처음부터 long으로 선언하는 게 맞나? 아니면 한 번 틀리고 아 오버플로우 문제구나 하고 고치는 게 맞나? 처음부터 예상하고 시작하는 건가?

 

 

코드 보기

import java.util.*;
import java.io.*;

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;
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            for(int j = 4; j <= n; j++) {
                dp[j] = dp[j-2] + dp[j-3];
            }     
            System.out.println(dp[n]);
        }
    }
}

 

 

---

 

다른 해결법 : 재귀함수 사용

일단 ... 재귀함수를 배우긴 했으나 어떻게 작동하는지 잘 모르겠음. 그래도 디버깅 하면서 어떤 식으로 동작하는지 조금은 알게 되었다. 

 

최대 dp[100]까지 가능하기에 101칸을 생성해야 한다(0은 안 쓰니까). for문을 사용해서 dp[1] ~ dp[100]까지 값을 넣고 바로바로 뽑아쓰는 방법도 가능하나, 만약 3 1 4 3 이런 식으로 주어지면 최대 배열 4까지만 사용하므로 나머지는 모두 필요가 없어진다. 메모리 낭비.

 

 

 

 

내가 참고한 분은 입력받은 숫자 부분이 dp[]에 없을 때(int라면 0, Integer라면 null일 때) 돌아가는 재귀함수를 생성하셨다. 

class 전체에서 사용하기 위해선 static 변수로 선언해야 함을 기억하자. 디버깅 돌리니까 처음부터 배열이 생성되어 있는 거 보고 신기했다. 

 

 

 

그럼에도 헷갈려서 직접 돌려본 결과를 들고 왔다. 아마 이게 재귀함수가 실행되는 순서일 거고, 스택에 쌓였다가 선입선출된다는 뜻이겠지? 빨간색은 return 되는 경우이다. 계속해서 n - (n-2) - 없다면 다시 (n-2) - 있다면 return - 다시 8로 갔다가 이번엔 n-3 ... 으로 반복되는 것을 알 수 있다.

 

 

코드 보기

import java.util.*;
import java.io.*;

class Main {
    // 클래스 전역에서 사용하기 위해 static 배열을 선언한다.
    // 클래스 변수는 전역 변수의 일종이지만, 반드시 전역 변수가 클래스 변수인 것은 아닙니다.
    public static long dp[] = new long[101];
    
    public static void main(String args[]) throws IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        
        int t = Integer.parseInt(br.readLine());
        
        while(t-- > 0) {.
            sb.append(pado(Integer.parseInt(br.readLine()))).append('\n');
        }
        System.out.println(sb);
    }

    public static long pado(int n) {
        if(dp[n] == 0) {
            dp[n] = pado(n - 2) + pado(n - 3);
        }
        return dp[n];
    }
}

 

---

 

이야

 

어렵다!

 

하지만 최근 푼 문제 중에 젤 재밌었다.

 

주석 있는 코드가 궁금하시다면

https://github.com/mjkim856/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/9461.%E2%80%85%ED%8C%8C%EB%8F%84%EB%B0%98%E2%80%85%EC%88%98%EC%97%B4

 

오늘도 감사합니다!

https://st-lab.tistory.com/127

https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0