(25.03.01)
문제 이해
일반적인 직선이 도미노, 곡선을 트로미노라고 하자.
정수 n을 입력 받으면 2xn에서 도미노를 만들 수 있는 길의 수를 반환하라. 이 때 반환 값의 크기가 크기에 10^9+7로 나눈 나머지를 리턴하라.(아마 정수형 크기 때문일듯)
모든 칸은 채워져야한다.
예시를 보고 문제를 이해했는데, 2xn개의 직사각형이 있고, 이를 테트리스 처럼 채워야하는데 사용가능한게
ㅁㅁ
랑
ㅁ
ㅁㅁ
밖에 없다는 거. 이 때 사용가능한 모든 경우를 구하라는 것이다.
문제 접근
TDD방식
우선 감이 잘 안잡힌다.
n=1일 때의 경우를 우선 구현해보자. 이 경우 ㅁㅁ 한가지밖에 없다.
n=2일 때의 경우를 우선 구현해보자. 이 경우 가로세로 ㅁㅁ 두개이다.
n=3일 때의 경우부터 복잡해시는데 이 경우는 문제 case1에서 5임을 얘기해주었다. 도미노로 3개, 트리미노로 2개가 가능하다.
class Solution {
public int numTilings(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 5;
return -1;
}
}느낌 상 피보나치처럼 규칙이 존재할 것 같기도 하다. n별 return을 확인하기 위해 제출하며 다음 케이스들을 얻어보자.
n=4일 때 11
n=5일 때 24
n=6일 때 53
n=7일 때 117
이제 규칙을 찾아보자.
1, 2, 5, 11, 24, 53, 117...
2배 +0, +1, +2?
1=1
2=12+0
5=22+1
11=52+1
24=112+2
53=242+5
117=532+11
규칙을 찾은 듯 하다. 11부터 첫번째 수가 더해진다.
이제 이 규칙을 구현해보자.
class Solution {
public int numTilings(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 5;
if(n==4) return 11;
if(n==5) return 24;
if(n==6) return 53;
List<Integer> index_table=new ArrayList<>();
index_table.add(1); index_table.add(2); index_table.add(5);
for(int i=3; i<n; i++)
index_table.add(index_table.get(i-1)*2+index_table.get(i-3));
return index_table.get(n-1);
}
}
규칙성이 30에서 적용되지 않음을 발견했다. 하지만 여기서 간과한게 있다. 반환값이 커질 것이기에 모듈로 10^9+7한 값을 사용하라고 했었다.
아니나 다를까 버퍼오버플로우가 발생했었다.
디버깅
리턴값이나 add하는 과정의 값에 단순히 modulo를 수행하는 것 만으로 문제가 해결되지 않았다.
그렇다면 index_table에 add하는 과정에서 오버플로우가 발생하지 않게끔 modulo연산을 수행하면서, 구하고자하는 값에 영향이 없게끔 해야하는데 어떻게 하면 좋을까?
우선 코드 백업
import java.util.*;
class Solution {
public int numTilings(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 5;
if(n==4) return 11;
if(n==5) return 24;
if(n==6) return 53;
final int MODULO_VALUE=10000007;
List<Integer> index_table=new ArrayList<>();
index_table.add(1); index_table.add(2); index_table.add(5);
for(int i=3; i<n; i++) {
int new_val=index_table.get(i - 1) * 2 + index_table.get(i - 3);
index_table.add(new_val%MODULO_VALUE);
}
return index_table.get(n-1)%MODULO_VALUE;
}
public void test(long result, long answer){
if(result==answer){
System.out.printf("passed! \t\tresult: %d, answer: %d\n", result, answer);
} else {
System.out.printf("fail! \t\tresult: %d, answer: %d\n", result, answer);
}
}
public static void main(String[] args){
Solution solution=new Solution();
solution.test(solution.numTilings(1), 1);
//solution.test(solution.numTilings(7), 117);
solution.test(solution.numTilings(30), 312342182);
}
}(25.03.02)
짧게라도 원인을 분석해보자. 현재 오버플로우가 발생하여 문제인 부분은 아래와 같다.
for(int i=3; i<n; i++) {
int new_val=index_table.get(i - 1) * 2 + index_table.get(i - 3);
index_table.add(new_val%MODULO_VALUE);
}무작정 modulo를 때리기에도 10^n꼴의 수가 아닌 10^7+7의 수라 고민이 된다.
부분적인 long타입 사용
new_val의 타입을 long으로 바꾸고 index_table에 add하기 전에 modulo한 int로 변환하면 어떨까?
오버플로우가 발생하지는 않았지만 312342182가 아닌 2335728이 나오게 되었다. 이는 기존에 long이 아닌 값을 사용했을 때와 같은 결과로, 다른 문제가 더 존재하는 듯 하다.
문제를 잘못읽었다. MODULO_VALUE가 10^7+7이 아닌 10^9+7이었다. long타입으로 다시 시도해보자.
여전이 버퍼 오버플로우가 발생했는데, MODULO_VALUE까지는 int범위인 2,147,483,647안에 들어가지만 연산 과정에서 더 큰 범위의 숫자가 들어가 문제가 발생한 것으로 추정된다.
전체 long타입 사용
범위 문제를 해결하기 위해 index_table까지 Long타입으로 바꾸어보자.
