프로그래밍38 [DP] BOJ_2133: 타일 채우기 도저히 규칙을 찾지 못해서 고생깨나 했던 문제이다. 결국 규칙을 못 찾아서 구글링을 통해 힌트를 얻고 나서야 비슷하게 도전해 볼 수 있었다. 사실 DP 관련한 문제들이 다 규칙을 찾기만 하면 무난하게 풀 수 있는데, 규칙을 못 찾아서 문제가 되는 것 같다. 규칙은 다음과 같다. 1. n이 홀수인 경우, 타일을 채우는 경우가 존재하지 않는다. 2. n이 짝수인 경우, '독특하게' 타일을 채우는 방법이 2가지씩 존재한다. 사실 여기까지는 나 스스로도 바로 찾아낼 수 있었지만, 이 이후로 이것을 규칙화하는 데 문제가 발생하였다. 그리고 그 문제를 해결해 주는 키워드는 '나누어서 생각하기' , 그리고 '함수처럼 생각하기' 였다. 우선, 3*n size의 벽을 채우는 경우의 수를 f(n)이라고 하자. 그렇다면 가.. 2022. 6. 29. [DP]BOJ_14002 가장 큰 증가하는 수열 찾기. 입력받은 수열을 저장하기 위해 배열 seq를, seq 배열의 각 원소를 최대값으로 하는 가장 긴 부분수열의 길이를 저장하기 위해 배열 dp를 만들어 사용하였다. 가장 짧은 증가하는 부분수열의 길이는 자기 자신, 즉 1이기 때문에 dp[1]=1로 설정하였다. 이후로 다음의 논리로 dp배열을 채워 넣었다. 만약 seq[j](jseq[i]인 경우에는 dp[i]가 'seq[i]부터 새로이 시작하는 경우' 인 1과, '반복문을 통해 이미 업데이트된 dp[i]의 값' 중 큰 값이 되어야 한다. 완성된 코드는 아래와 같다. package DP; import java.io.*; import java.util.Stack; public class BOJ_14002 { static int[] .. 2022. 6. 27. 이전 1 ··· 7 8 9 10 다음
