"꾸준하게, 지속하자 "

매우어려웠다. 무슨소리인지 접근조차 못했다. 그나마 이해한 것은 5원을 만드는 경우의 수= 1,2원을 통해 5원을 만드는 수(dp[5]) + 5원을 통해 5원을 만드는 수(dp[0]=dp[5-0]. 6원을 만드는 경우의 수= 1,2원을 통해 6원을 만드는 수(dp[6]) + 5원을 통해 6원을 만드는 경우의 수(dp[1]=dp[6-5]). 7원을 만드는 경우의 수= 1,2원을 통해 7원을 만드는 수(dp[7]) +5원으로 7원을 만드는 경우의 수(dp[2]=dp[7-5]). 이렇게 된다. ** 여차저차 해서 난 이해했다고 착각했던 거 같다. 위에 밑줄친 부분인 k값(만들려는 값)에서 coin의 값어치를 뺀 값을 만드는 경우의 수를 더해주는 것이 왜 어째서 해당 coin의 경우를 더해주는 것인지 이해가 잘..

우선 어려웠다. 애초에 dp 배열을 1차원으로 구하면 될 줄 알았는데 그게 아니였다. 그리고 배열의 기준을 첫번쨰 자리부터 차근차근 올라가면서 앞 자리수보다 크거나 같은 수를 구하는 방식이 아니라, 미리 맨 마지막 자리에 올 수를 정해놓고, 앞 자리수에 올수 있는 수를 한정해주는 방법을 쓴다. 그래고 매우 어려운 것이, 우선 난 dp문제를 풀때의 철칙이 1. dp[i]=num의 정의, 2. dp[N]과 dp[N-1]의 관계를 파악해서 프로그래밍을 하였는데 그래서 난 계속 1차원 배열로 풀려고 했었다. 그런데 이젠 dp 배열이 2차원으로 푸는 문제인지 아닌지 0순위로 판단후, 파악해야겠다. 우선 이 문제에서 dp[i][j]=num 의 정의는 "i 번째 자리수에서 맨 마지막 자리에 오는 숫자가 j 일때 가능..

우선 DP 문제를 많이 연습해서 그런지, 처음보다는 문제 풀이 방법이 비교적 쉽게 떠올랐다. 우선 DP[i]=num 의 의미를 정의하고 시작하면 풀이법이 자연스럽게 떠오르기 마련인데, 난 i개를 뽑을때 최댓값 num이라고 정의했다. 그리고 DP[N]과 DP[N-1] 의 관계를 나타내면 끝인데, 내가 dp[1]부터 해본 결과 dp[n]= 두 수를 더해서 n을 만드는 수를 인덱스를 가지는 dp배열의 두 값의 합들중 가장 큰 값, 입력받은 arr[i]과 비교해서 큰 값이였다. 다시 쉽게 풀면 dp[5]를 구하려면, dp[1]+dp[4], dp[2]+dp[3]중 가장 큰 값과 숫자카드팩의 갯수를 한번에 맞출수 있는 arr[i] 의 값중 큰 것이다. 왜냐하면 내가 dp[i]는 i를 뽑을 때 가장 큰 값으로 정의했..

문제는 우선 처음 아이디어를 내고 DP[i] =num 이 무엇을 의미하는지와, N-1항에서 N항으로 어떻게 갈수 있는지를 파악하기만 하면 쉽게 풀린다. 두가지 풀이법이 있다. 첫번째는 내 풀이법인데 난 이것이 DP[i]의 정의를 더욱 더 직관적으로 이해할수 있는 코드라고 생각한다. 물론 시간초과나서 틀렸지만. 하지만 알고리즘 원리는 똑같으니 같은 해답이다. 나는 DP[i]=num 의 정의를 N부터 시작해서 연산을 통해 i를 만들수 있는 연산의 최솟값 num 으로 정의했고, 다른 좀더 빠른 방식으로는. i를 1로 만들수 있는 최소연산횟수 num으로 정의했다. 내가 한 방법이 조금 더 문제의 조건에 직관적이긴 하지만, 시간초과가 난게 아마 2중 for문으로 현재 인덱스보다 크고 N보다 작은 것중에 2나 3으..

우선, '비용의 최솟값' 을 구하라는 말이 나왔으므로, DP로 풀어야 한다. 그런데 그 전까지는 DP배열이 1차원 배열이였는데 지금은 상황이 조금 다르고, DP[i][j]가 무엇을 가르키는지 구체적으로 정의하는 것이 매우 중요하다. 이전 포스트에서도 꾸준히 강조하는 말하지만 DP문제에서 무엇을 DP값으로 정할건지가 핵심이다. 나는 이 문제에서 2차원 배열로 주어진 입력값(행:N번째 집 열: 빨,초파)에서 결국 맨 마지막으로 선택되어질수 있는 색깔, 마지막 N번쨰 항에을 조건으로 삼아 DP값을 정의하였다. 우선 문제의 특수한 조건들 때문에 마지막 N번집의 색깔은 빨, 초, 파, 중 한개만 가능하다. 즉, 경우의 수를 3개로 나누어(마지막 색이 빨강부터 칠해질건지, 파랑부터 칠해질건지..) 모든 경우의 수를..

일단 매우 어려웠다. 그나마 이거 풀기 전, 2차원 배열의 DP를 활용하는 문제인 1149번 RGB 거리 문제를 풀지도 못하고, 정답을 한번 봐서 그런지, 접근법은 대충 맞았다. 그러나, 진짜 이런 2차원 배열의 DP활용 문제를 처음 봤더라면 접근조차 못했을 것이다. 우선 가장 핵심적인 아이디어는 "아래로 내려갈수록, 가장 최대의 값만 선택하면 안된다. 즉, 그리디로 풀수 없다." -> 그렇기에 모든 경우의 수를 다 따져야 된다.-> 처음부터 아래로 내려가는 규칙을 찾자. 이다. 노트에 그려 보면 맨 왼쪽노드와 맨 오른쪽 노드는 바로 그전 계층의 노드값을 그대로 받는다. -> if(j==0){ dp[i][j]=arr[i][j]+dp[i-1][0]; } if(j==i-1){ dp[i][j]=arr[i][j..

전형적인 그래프 탐색 문제이며, "최단" 거리+미로의 탈출을 구하여야 함으로 BFS를 써야 한다. 최단 거리를 구하는 문제에서, DFS가 아닌 BFS를 쓰는 이유는 한가지 계층(똑같은 길이나 방법)을 이용해서 한번 이동을 한 거리가 모두 같음이, 자연스럽게 구현이 되기 때문이다. 또한 같은 계층으로써 방문한 노드가 목적지랑 같을시, 계층 한번이동할때(큐에 넣을때) 넣어준 카운트 값으로 쉽게 최단거리를 출력할 수 있다. 또한 미로의 탈출은 깊이우선 탐색을 하게되면, 해답을 찾지못해도, 계속 깊이가 끝날때까지 탐색을 하기에, 비효율 적이다. 그래서 난, BFS를 통해 이문제 풀이법을 구현해 보았다. 그러나 내가 이전 포스트에서 쓴 촌수문제에서, 큐에 넣을때(한번 계층이동이 이루어질때) 바로 카운트값을 더해주..

우선 증가하는 부분수열 문제를 dp로 풀수 있다면 이 문제또한 쉽게 풀수 있을것이다. 애초에 앞의 상자보다 값이 작으면 뒷 상자에 넣을수 있다는 조건이, LIS 문제의 정의와 같다. 다만 주의해야 할 점은, if 조건문에서 단순히 이전값이 현제 인덱스의 값보다 작을시, 이전 dp값에 +1한 것을 현재dp값에 더해주는것을 가능하게하는 조건으로 작용하는 것이 아니라,(아래의 코드에서 dp[i]=dp[j]+1 부분) 이전 dp의 값+1 한 것이 현재 dp의 값보다 커야한다라는 조건도 있어야 된다는 것이다. 나도 처음에 이 조건이 왜 필요한지 생각하느라 애를 참 많이 썼는데, 간단히 설명하자면 이전 값이 현재의 값보다 더 작다는 조건에 만족하는 중복된(같은수)를 카운트하는것을 방지하기 위한 장치이다. 예를 들면..