📌 문제

[9641] 파도반 수열

아래 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

⬇️ 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

⬆️ 출력

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

💡 코드

✅ 처음에 문제랑 사진을 보고 뭔 말인가 했는데 예시로 주어진 수열 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 을 보고 바로 규칙을 찾을 수 있었다!

언뜻 보기에는 피보나치 수열과 비슷한데, f(n-1) + f(n-2)를 수행하는 피보나치와 달리 파도반 수열은 f(n-2) + f(n-3)을 수행한다! 로직 자체는 피보나치 수열과 동일하게 처음의 세 삼각형 memo[0], memo[1], memo[2]을 1로 정의하고, 이후 요소들을 memo[i-2] + memo[i-3]을 통해 연산을 수행하고 결과값을 저장해준다.

이 때, 테스트 케이스가 여러개이므로 이전 케이스에서 이번 케이스의 값을 이미 연산했다면 굳이 다시 for문을 돌릴 필요 없이 저장된 결과값을 리턴하게 했다.

❌ 하지만 아래 코드를 제출하면 오답 처리가 되는데,,

import java.io.*;
import java.util.*;
public class Main {
	
	static int[] memo = new int[100];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		memo[0] = memo[1] = memo[2] = 1;
		
		for(int i=0;i<t;i++) {
			int k = Integer.parseInt(br.readLine());
			sb.append(dp(k)).append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static int dp(int n) {
		
		if(memo[n-1] != 0) return memo[n-1];
		
		for(int i=3;i<n;i++) {
			memo[i] = memo[i-2] + memo[i-3];
		}
		return memo[n-1];
	}
}

✅ 왜 오답 처리가 됐을까 생각해보다가 설마 100까지 더한 값이 int 범위에서 오버플로우인가? 라는 생각에 memo[]와 dp(n)의 리턴 타입을 long 타입으로 바꿔줬고,, 바로 정답 처리가 되었다 ^^,, 코드 짜기 전에 생각했나요?

...
	
	static long[] memo = new long[100];
	
...
	
	static long dp(int n) {
		...
	}
}