[BOJ] 2193. 이친수 (Java)

문제 링크 / level: Silver III

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

2193번: 이친수

 

 

내가 생각한 풀이

동적 계획법(DP) 문제를 하나만 더 풀어보자 싶어서 건드린 문제. 이것도 초고수 형님들의 블로그 추천문제에 있어서 도전해봤다. 이번 문제의 목표는 처음부터 끝까지 온전히 나의 힘만으로 점화식을 유도해보자! 하는 것이었고, 그 목표를 이뤘다 (뿌듯🤗🌸)

 

점화식을 유도해보자!!

▲열심히 점화식을 유도한 흔적..

 

내가 유도해낸 점화식은 d[i] = d[i-2] * 2 + d[i-3] 였다. 더 간단한 수식이 있다면 그걸 찾아보고 싶기도 했지만, 당시 나는 내 힘으로 점화식을 찾아냈다는 것만으로도 감동실화~~(❁´◡`❁) 이러고 있어서 더 건드려 볼 생각은 차마 하지 못했다.

---

그. 런. 데!!

백준 사이트에 코드를 넣고 돌려보니...

첫 번째 시도의 결과는 틀렸습니다. 였다. (아니 왜 때문에???! 나의 완벽한 점화식과 알고리즘이!!!😂)

그 이유인 즉슨, N=90까지 가능하기 때문에 memo 배열(*메모이제이션을 위한 배열)의 데이터 타입을 int type으로 해서는 안됐다. 그러면 N이 일정 숫자 이상으로 커지면 터져버린다. 그래서 호다닥(메다닥) long type으로 고쳐줬다.

 

그 뒤에 다시 시도해본 결과 런타임 에러가 떴다. 나중에 짝꿍에게 물어보니 런타임 에러는 대부분 배열 인덱스 문제라고 했다.

아무튼 당시 나는 잘 모르기 때문에 질문 검색에서 이것저것 여러 글을 뒤져봤다. 그 결과 기본적으로 N=1이나 N=90일 때처럼 코너에 있는 값을 넣어봐야 한다는 조언의 글을 읽었고...

 

내 코드에 N=1을 넣어본 순간 배열의 인덱스를 벗어났다는 에러가 떴다.

long[] d = new long[N+1];
d[1] = 1;
d[2] = 1;
d[3] = 2;

당시의 내 코드는 이랬는데, 만약 N=1일 경우 d라는 메모이제이션용 배열의 사이즈가 2다. 즉, 인덱스로는 0과 1만 존재한다. 그런데 d[2]와 d[3]에 값을 넣으려고 하니 에러가 난 것이다. 물론 이 현상은 N=2일 때도 마찬가지로 발생한다. (그 전에는 N=3부터만 넣어봐서 몰랐음. N=90일 때는 잘 됐었고😂)

 

그래서 도대체 어떻게 해야하지!? 싶었던 나는 최악의 코드를 짜서 어찌저찌 통과는 시킬 수 있었다.

long[] d = new long[N+1];
d[1] = 1;
if(N>=2) {
	d[2] = 1;
	if(N>=3) {
		d[3] = 2;
		if(N>=4) {
			for (int i = 4; i <= N; i++) {
				d[i] = d[i-2] * 2 + d[i-3];
			}
		}
	}
}

내가 짜놓고도 이건 아닌데... 싶었지만 당시에는 더 좋은 방법이 생각나지 않아서 저렇게 짰고, 백준 사이트에서도 통과할 수 있었다. 하지만 여전히 이건 좀 아닌데 싶었고.. 좀 더 고민을 해봤다.

그리고 그 결과 한결 깔-끔해진 코드!

// 핵심 코드
long[] d = new long[N+3];
d[1] = 1;
d[2] = 1;
d[3] = 2;
for (int i = 4; i <= N; i++) {
	d[i] = d[i-2] * 2 + d[i-3];
}

long[] d = new long[N+3] 이 부분을 new long[91]으로 할 수도 있기는 한데, 그러면 낭비되는 메모리 공간이 너무 많지 않을까 싶어서 나름대로 머리 굴려서 생각해낸 최후의 방법이다. 이제야 좀 만족스러운 코드가 완성되었다^_^

비록 new long[91]로 했을 때(아래)와 new long[N+3]으로 했을 때(위) 큰 차이는 없지만 그래도 미세하게나마 줄었으니까...? 나는 만족할게요...?👩🙆‍♀️❤️

 

 

p.s. 그런데 말입니다. 알고보니 이 문제가 곧 피보나치 수열과 같다고 하더라고요...?🤨 똑똑이들 부럽다~ 내 점화식은 복잡한데 ㅋㅋㅋ 그래도 내가 직접 구해낸 것에 만족합니다 ㅠㅠ (po정신승리wer)

 

▼아래 더보기를 누르면 코드 전체를 볼 수 있습니다.

[코드 보기]