[백준 11727] 2×n 타일링 2 [C]
풀이 "백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도.. 2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다. N 타일 dp[1] 2 11 2, T 3 3 111 12,1T 21,2T 5 4 1111 112,11T 121,1T1 211,T11 22,TT 2T,T2 11 5 11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21 21 6 " 43 7 " 85 8 " 171 N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다. 소스코드 #include #define MOD 1..
2021. 8. 8.
[백준 11660] 구간 합 구하기 5 [C]
풀이 편의를 위해 합 또한 2차원 배열로 저장을 해주었다. 다음은 문제의 예제로 주어진 표에 대한 누적 합을 저장한 배열 sum이다. [x, y]가 의미하는 바는 [1, 1] 부터 [x, y]까지의 누적 합이다. 만약, [2, 3](초록색), [4, 4](노랑색) 구간의 합을 구할 때, [2, 3]을 기준으로 불필요한 누적 합인 [1, 4](=10), [4, 2](=24)을 빼주면 된다. 하지만, [1, 4]와 [4, 2]를 빼는 과정에서 공통된 누적 합(분홍색)을 두번 빼므로, [1, 2]를 더해주어야 한다. 정리하면 다음과 같다. // input :: 4 4 2 3 sum[x2][y2]- sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] // ex) [4, 4] -..
2021. 8. 3.
