Memento's Programming

문제 2×n 크기의 직사각형을 1×2, 2×1, 2 x 2 타일로 채우는 방법의 수를 10007로 나눈 나머지를 출력하는 프로그램을 작성하시오. 풀이과정 이 문제는 지난 11726번 2xn 타일링 문제를 참고하면 좋을 것 같습니다. 단지 여기서 정사각형 모양의 2 x 2 타일이 추가된 것 뿐이지요. 지난 포스팅에서는 n = 3 일 때, n = 2 일 때 채웠던 방법들에 2 x 1 타일을 붙여주었습니다. 또한, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 정사각형 모양으로 붙여주었습니다. 여기서 우리는 추가로 n = 1 일 때 채웠던 방법들에 2 x 2 타일을 붙여줄 수 있습니다. 즉, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 붙여줄 수도 있고, 2 x 2 타일을 붙여줄 수 있..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 10007로 나눈 나머지를 출력하는 프로그램을 작성하시오. 풀이과정 이 문제 역시 DP로 풀 수 있는 문제입니다. n = 1 일 때는 2 x 1 타일로 채우는 한 가지 방법이 있습니다. n = 2 일 때는 2 x 1 타일 2개로 채우거나, 1 x 2 타일 2개로 채우는 방법이 있겠지요. 그럼 n = 3 일 때는 어떨까요? n = 2 일 때 채웠던 방법들에 2 x 1 타일을 추가할 수 있을 것입니다. 또한, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 정사각형 모양으로 추가할 수 있습니다. 이런식으로 (n - 1) 일 때의 가짓수와 (n - 2) 일 때의 가짓수를 더하면 n일 때의 가짓수를 쉽게 구할 수 있습니다. 이를 ..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이과정 먼저 정수 1의 연산 최솟값은 0입니다. 정수가 2나 3의 배수가 아닌 경우에는 무조건 3번의 연산을 수행해야합니다. 하지만 정수가 2나 3의 배수라면 두가지 선택이 있습니다. 1) 1을 뺀다. 2) 2나 3으로 나눈다. 그럼 1)과 2)에 대한 연산을 각각 수행해서 최솟값을 찾으면 됩니다. 이렇게해서 입력받은 정수 N까지의 연산의 최솟값을 구해 출력하면 될 것입니다. 코드 1 2 3 4 5 6 7..