내가 처음 DP를 접할 때, 좋은 접근 방법 중 하나가 큰 문제와 가장 작은 문제로 구분하는 것이였다. 이 문제 또한 큰 문제와 작은 문제로 나눌 수 있는데, 가장 작은 문제는 맨 뒷 블럭에 올수 있는 형태로 구분하였다. 이 문제의 경우엔 총 2가지인데, 1*2 타일을 높이로 두개 쌓거나, 2*1 타일을 하나 두는 것이다. 1 * 2 타일의 세로로 두개를 올린 경우 가로의 길이는 (n-2)가 되고, 2 * 1 타일의 경우엔 가로의 길이는 (n-1)이 된다. 따라서 아래와 같이 점화식을 작성하면, 타일의 갯수를 구해낼 수 있다. D[n] = f(n-1) + f(n-2); import java.io.*; public class D11726 { public static void main(String[] arg..
우선 이 문제를 풀기 앞서 아래의 문제를 풀지 않았다면 해당 문제를 풀어보고 나서 이 문제를 풀어볼 것을 추천한다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 우선 이 문제를 풀 때, 1463번과 접근방법은 동일하다. 근데 지금 추가로 문제에서 요구하는 것은 내가 연산을 어떻게 진행했는지, 기록을 해야한다. 나는 이 문제를 해결하기 위해서, 연산을 3으로 나누던 2로 나누던 1을 빼던, 큰 문제와 작은 문제의 값은 무조건 1의 차이가 난다는 것을 이용했다. 아래는 미지수 X를 1로 만드는데 드는 최소 연산 횟수를 구하는 코드이다. private stat..
우선 DP는 큰 문제를 작은 문제로 나누고, 그 작은 문제들의 값으로 큰 문제를 구하는 것이다. Dinamic Programin이라고도 하며, 동적계획법이라고도 한다. DP를 풀 때 Bottom Up과 Top Down 방식이 있다. Bottom up은 작은 문제들부터 계산해서 큰 문제를 구하는 것이고, Top Down은 이의 반대이다. 이 둘의 차이는 크게 없지만 약간은 다르다. Top Down 방식은 재귀하면서 스택을 쌓아가기 때문에 StackOverFlow 에러가 뜰 수 있다. 따라서 자바, C언어는 딱히 상관 없지만 파이썬은 Top Down보다 Bottom Up이 더 낫다고 생각한다. 나는 자바 언어고, Top Down 방식이 더 마음에 들어서 이 방식으로 공부를 하려고 한다. 그럼 문제 풀이를 해..
