점화식
-
프로그래머스 Lv.4) 3xn 타일링알고리즘/프로그래머스 2020. 5. 14. 23:45
3xn 타일링 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 타일링 시리즈 문제로 DP 문제이다. 하지만, 점화식 세우는데 애를 먹었다. 우선, 홀수의 경우 타일을 채울 수 없다는 것과 dp[n] = dp[n-2]*3 부분까지는 쉽게 세울 수 있었다. n이 2씩 증가할 때마다 새롭게 생기는 3x2의 직사각형 부분을 채우는 경우의 수가 3가지기 때문에 이 전보다 3배의 경우의 수가 더 생긴다. 이해하기 힘들었던 부분은 n이 4마다 새롭게 생기는 2가지 경우의 수였다. n이 4 증가할 때마다 생기는 이 부분 때문에 많은 고민을 하게했고, 다른 분들이 포..
-
프로그래머스 Lv.3) 종이접기알고리즘/프로그래머스 2020. 5. 14. 00:35
종이접기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 (코드 1, 코드 2) 문제를 보자마자 점화식이 필요한 문제라고 생각했다. 그래서 처음 생각한 점화식은 n => n-1까지의 결과를 두 번 반복하고 끝에 1이 들어간다고 생각했다. 주어진 테스트 케이스만 봤을 때는 답이 나오기는 했다. 하지만 제출 결과는 0점이었다. 점화식이 틀렸다는 것을 알아차리고 새로운 점화식을 세우려했다. 하지만 어제 과음.. 다른 분의 점화식을 참고하니까 2^(n-1)을 기준으로 대칭되는 인덱스는 서로 다른 값을 가지고 있다는 식을 보았다. 물론 기준점(2^(n-1)) ..