tose33

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net d[n] : n 이라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수. 주어진 연산: X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 그렇다면 d[n-1]은 n-1이라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 최소 횟수이다. n - 1에서 1을 더하는 연산(3번째 연산)이 1회 수행되면 n이기 떄문에 d[n] = d[n - 1] + 1 같은 방식으로 d[n / 2]는 n / 2 라는 숫자를 주어진 연산으로 1로 만들 수 있는 연산의 ..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이번에는 2 x n 직사각형을 2 x 1, 1 x 2에 추가로 2 x 2 타일로 채우는 방법의 수를 구하는 것이다. 마찬가지로 d[n]은 d[n] : 2 x n 직사각형을 2 x 1, 1 x 2, 2 x 2 타일로 채우는 방법의 총 가지 수 2 x n 타일링 1번 문제에서 2 x 2 타일만 추가됐다. 그리고 2 x 2 타일을 추가하는 건 그냥 1 x 2타일 두 개를 붙인 것과 같다. d[n] = d[n - 1] + d[n - ..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2 x n 크기의 직사각형을, 1 x 2, 2 x 1 타일로 채울수 있는 방법의 수를 구하는 문제. 처음 풀어본 dp 문제인데 생각을 dp스럽게? 바꾸는게 어려운것 같다. dp 문제는 점화식이 중요하기 때문에 다 풀고 보면 코드는 매우매우 간단한데 그 점화식 알아내기가 참 힘든것 같다. 많이 풀다 보면 딱 보면 어 이거 그문제랑 비슷한데? 이렇게 나온다는데 .. 일단 2 x n 크기의 타일이 있다고 생각해보자 이 2 ..