프로그래밍/백준 복기31 [DP] BOJ_14501: 퇴사 난이도가 실버3로 그리 어렵다고 할 수 없는 문제임에도 엄청나게 애를 먹었다. PS를 하다 보면 이상한 데 꽂혀서 중요한 곳을 지나치고 어문 곳을 계속 빙빙 돌 때가 있는데, 그런 경우가 가장 난감한 것 같다. 이 문제의 경우에는 내가 '만약 첫째 날에 잡혀 있는 일정이 너무 오래 걸려 잡을 수 없는 예약인 경우' 를 고려하지 않고, 다른 곳에서 틀렸다고 쓸데없는 확신을 하여 여기저기 손대 보다가 망한 문제이다. 아마도 지금까지 풀어 온 '~한 ~수열 찾기' 류 문제들이 당연히 첫 번째 memoization은 자기 자신, 혹은 1이 되는 문제들이었기에 이런 실수를 한 것 같다. 우선 문제를 풀기 위해 소요 날짜를 나타내는 duration 배열, 보수를 나타내는 payment 배열, 그리고 memoizat.. 2022. 6. 29. [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 ··· 5 6 7 8 다음
