백준 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.
