문제 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 풀이 정말 어려웠지만 재밌는 문제였다. 풀이법이 잘 생각나지 않지만 생각만 잘한다면 코드 길이가 매우 짧고 명료하게 해결할 수 있다. 이 문제는 DP를 이용하면 해결할 수 있다. 나는 DP 배열을 다음과 같이 정의했다. DP[0][i][j] = (i,j) 좌표에 세로로 들어오는 경우의 수 DP[1][i][j] = (i, j) 좌표에 가로로 들어오는 ..
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 이 문제는 간단한 DP 문제였다. maxDp와 minDP를 따로 나누어서 해결하면 간단하다. 우선, maxDp의 경우는 아래와 같은 점화식을 세우면 된다. maxDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최댓값 ( 0
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 부분 수열(LIS) 문제이다. LIS에 대해서는 다음 게시글이 설명을 자세하게 있으니 참고하자 https://sskl660.tistory.com/89 [Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence) *최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 ..
문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 처음에는 단순 DFS로 문제를 접근했다. 하지만 DFS를 사용하면 시간 초과가 발생한다. 이 문제는 DP를 사용해서 해결해야 한다. 점화식을 아래와 같이 세우면 된다. dp[i][j] = i번째 집을 j 색깔로 칠할 때 비용의 최솟값 dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) // 이때 j와 같은 숫자는 제외..