Algorithm/DP

문제https://www.acmicpc.net/problem/1149 여담예전에 풀었을 때는 풀이를 참고해서 풀었는데 이번에는 스스로 풀었다..! 실력이 크게 는 것 같지는 않지만 그래도 좀 뿌듯 ㅎㅎ 근데 DP 문제라는 것을 알고 있어서 쉽게 풀었지, 몰랐다면 헤맸을 것 같다. 각 유형을 공부한 뒤에 랜덤으로 문제를 푸는 연습도 꼭 해야 되겠다..! 풀이모든 집을 칠하는 최소 비용을 구하기 위해 1번 집부터 N번 집을 칠하는 최소 비용을 누적하여 테이블을 채워 나가면 된다. 이때, 연속된 집은 같은 색으로 칠하지 못한다. 따라서 색칠하는 경우의 수는 다음과 같다.현재 집에 빨간색을 칠하는 경우이전 집은 초록색 또는 파란색이 칠해져 있어야 함dp[i][0] = Math.max(dp[i][1], dp[i]..

1463: 1로 만들기🔗 문제 링크1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 각각 나누어서 점화식을 세워야 함1을 빼는 경우의 값으로 초기화: dp[i] = dp[i - 1]3으로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 3] + 1)2로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 2] + 1)BFS 탐색도 가능할 것 같아서 시도했는데 BFS 탐색으로도 최소 연산 횟수를 구할 수 있음탐색하고 있는 수가 1이 되면 탐색을 종료해야 함dist[N]이 아니라, dist[1]의 값이 N에서 1까지의 최소 연산 횟수이므로 주의할 것!더보기24.06.24 풀이DP 풀이import java.io.*;public clas..

문제https://www.acmicpc.net/problem/11660 여담저번에 풀었던 문제임에도 불구하고 까먹어서 결국 풀이를 참고했다. 그때도 완전히 익히지 않고 넘어갔다는 뜻이겠지..? 이런식으로 설렁설렁 넘어간게 대체 몇 개인지🤦🏻‍♀️ 이번에는 좀 익히자.. 풀이2차원 테이블을 사용해서 누적합을 구하면 되는 문제이다.  우선 배열의 값들을 입력받은 후, 아래의 점화식을 이용해 dp 테이블을 채워야 한다.dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j] 누적합을 이용해 dp 테이블을 채운 후, 이제 원하는 영역의 누적합을 구해야 한다. 이를 위해 다음 그림과 같이 각 구간의 누적합을 더하고 빼주면 된다. 코드import java.i..

문제https://www.acmicpc.net/problem/10844 여담저번에 풀려고 시도했다가 풀지 못해서 그냥 나뒀던 문제였다.. 그치만 계속 외면할 수는 없어서 풀이를 참고해서 풀었다.표를 그려서 풀었다면 규칙을 찾아낼 수 있었을텐데 계속 다른 방식으로 삽질해서 아쉬웠다😂 DP 오랜만에 푸니까 너무 어렵다..!! 풀이이 문제는 규칙만 찾아내면 쉽게 풀이할 수 있다. 참고한 블로그의 표를 보고 쉽게 이해했으므로, 나도 표를 이용해서 설명하려고 한다.해당 문제는 인접한 모든 자리의 차이가 1이다. 따라서 0에서 9까지의 숫자 뒤에 올 수 있는 숫자들의 특징은 다음과 같다.앞의 자리가 0 ⇒ 다음 자리는 무조건 1앞의 자리가 9 ⇒ 다음 자리는 무조건 8앞의 자리가 1 ⇒ 다음 자리는 0 또는 2앞..