22.05.13. 풀었던 문제들

1. 가장 긴 팰린드롬

시간 초과가 계속계속 난다... 그래서 최대한 줄이기 위해 긴 문자열부터 검색을 진행하고, 추가 함수도 사용하지 않고 s.substr도 사용하지 않고 index와 length만으로 검사를 하는데 잘 안된다...으으으으윽 내일 다시 봐야겠다.... 그리고 lv3 오니까 좀 어려운 문제가 많아지긴 했다.

​

2. 2 x n 타일링

문제를 잘 살펴보면

n개를 채우는 방법

- 1개짜리 n개로만 채우는 방법 = nPn (1)

- 2개짜리 1개, 1개짜리 n-2개 = (n-1)! / (n-2)!

- 2개짜리 2개, 1개짜리 n-4개 = (n-2)! / (n-4)!

이렇게 된다. 그러나 이렇게 구하면 답이 없는게 n이 6만이기 때문이다. 따라서 다른 방식을 취해주어야 한다.

​

잘 살펴보면 n이

1개 : 1 (1개짜리 1개)

2개 : 2 (1개짜리 2개 / 2개짜리 1개)

3개 : 3 (1개짜리 3개 / 1개짜리 1개 + 2개짜리 1개)

4개 : 5 (1개짜리 4개 / 1개짜리 2개 + 2개짜리 1개 / 1개짜리 0개 + 2개짜리 2개)

5개 : 8 (1개짜리 5개 / 1개짜리 3개 + 2개짜리 1개 / 1개짜리 1개 + 2개짜리 2개)

이다. dp[i] = dp[i-1] + dp[i-2]인데, 이렇게 되는 이유는

1) i-2번째 것의 마지막에 가로로 눕힌 막대를 2개 추가하는 경우

2) i-1번째 것의 마지막에 세로로 세운 막대를 1개 추가하는 경우

를 합쳐준 것이 i번재 것이 되기 때문이다. 즉, 피보나치다!