백준 3673번 :: 나눌 수 있는 부분 수열 - C++
힌트 1. i번째부터 j번째까지 연속하는 부분수열의 합을 \(A_{i, j}\)라고 하면, \[A_{i, j} = A_{1, j} - A_{1, i}\] 이므로 '연속하는 부분 수열의 합'을 '두 개의 부분 수열 누적합의 차'로 표현할 수 있다. 2. 1번의 내용을 응용하면, \[A_{i, j} \, mod \, d = (A_{1, j} - A_{1, i}) \, mod \, d = 0\] 이고, 이는 곧 \[A_{1, j} \, mod \, d = A_{1, i} \, mod \, d\] 이므로 '연속하는 부분 수열의 합이 d로 나누어 떨어지는 것'은 '두 부분 수열 누적합을 d로 나눴을 때의 나머지가 동일한 경우'와 같다. 3. 추가로 부분 수열 누적합의 나머지가 0인 경우 해당 부분 수열은 독자적으..
2023. 8. 7.
백준 11726 : 2×n 타일링 - C++
어제 소개해드렸던 9095번 : 1, 2, 3 더하기와 비슷한 문제입니다. 경우의 수들을 나열해서 적어보고 적절한 점화식을 찾아봅시다! 더보기 편의상 가로 길이가 1인 타일을 하나 배치하는 경우를 1로, 가로 길이가 2인 타일을 위 아래 두 개 배치하는 경우를 2로, 명칭하도록 하겠습니다. 2x1 직사각형에 타일을 채우는 경우 : 1 2x2 직사각형에 타일을 채우는 경우 : 1, 1 / 2 2x3 직사각형에 타일을 채우는 경우 : 1, 2 / 1, 1, 1 / 2, 1 2x4 직사각형에 타일을 채우는 경우 : 1, 1, 2 / 2, 2 / 1, 2, 1 / 1, 1, 1, 1 / 2, 1, 1 힌트가 보이시나요? 2x3의 경우, 2x1 경우의 오른쪽에 2를 더한 것과 2x2 경우의 오른쪽에 1을 더한 것..
2023. 2. 5.
백준 9095 : 1, 2, 3 더하기 - C++
1, 2, 3 갯수를 일일히 구하는 것은 비효율적인 접근이겠습니다. 1부터 n을 하나씩 늘려가면서 n을 1, 2, 3의 합으로 나타낼 수 있는 경우들을 직접 적어보고 적절한 점화식을 찾아봅시다. 더보기 n이... 1 인 경우 - 1 2 인 경우 - 1, 1 / 2 3 인 경우 - 1, 1, 1 / 1, 2 / 2, 1 / 3 4 인 경우 - 1, 3 / 1, 1, 2 / 2, 2 / 1, 1, 1, 1 / 1, 2, 1 / 2, 1, 1 / 3, 1 위 경우들을 살펴보면, n이 1인 방법의 뒤에 3을 붙이고, 2인 방법들의 뒤에 2를 붙이고, 3인 방법들의 뒤에 1을 붙이면 n이 4인 방법들을 완성할 수 있다는 규칙이 보입니다. 즉, A(n)이 n을 1, 2, 3의 합으로 나타낼 수 있는 경우의 수라고 ..
2023. 2. 4.
