본문 바로가기

다이나믹 프로그래밍27

[코틀린, 자바] 백준 14651 - 걷다보니 신천역 삼 (Large) (boj kotlin java) 문제 : boj14651 우선 3의 배수를 판정하는 방법부터 알아보자. 이 경우 수 A의 모든 자리의 숫자의 합이 3의 배수라면 A도 3의배수이다(정수론). 그럼 이 문제는 N자리 숫자에 대해, N번의 선택을 거친 결과 모든 자리 수의 합이 3의 배수인 경우의 수를 찾는 문제인 셈이다. 물론 단순하게 brute force로 찾아보려 한다면 O(3^33333)이 필요하므로 불가능하다. DP로 생각해보자. dp[a][b]를 a번째 자리수까지 더했을 때의 합을 3으로 나눈 나머지가 b인 경우의 수로 정해보자. 그럼 a가 5일때까지만 살펴보자. (N=5) 1. 우선 a=1 일 경우 다음과 같이 될 것이다. 또 이렇게 두면 '0으로 시작하는 수는 만들 수 없는 수 이삼' 부분을 별도로 처리하지 않아도 되기 때문에.. 2022. 7. 10.
[코틀린, 자바] BOJ 15645 - 내려가기 2 (boj kotlin java) 문제 : boj15645 ps. 코틀린의 경우 대강 인터넷 검색해서 문법을 익혔으므로 아직 늅늅이 상태여서 많이 어색하게 짰다. 이 문제의 경우 dp로 풀면 쉽게 풀린다. 알아야 하는 정보는 바로 직전 3칸의 합계 뿐이다(시작할때는 당연히 셋 다 0이라고 치면 된다.). N개의 줄을 입력받으면서, 매번 해당 칸으로 올 수 있는 값 중 최대와 최소값을 갱신 후에 현재 줄에서 입력받은 값을 더해주면 된다. dp[a][b]가 a라인까지 입력받았을 때 b번째(0,1,2로 3개) 칸까지의 최대합계라고 해보자. 그렇다면 dp[x][0] = max(dp[x-1][0], dp[x-1][1]) + 입력받은 0번째 값 dp[x][1] = max(dp[x-1][0], dp[x-1][1], dp[x-1][2]) + 입력받은 .. 2022. 7. 9.
[자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26.
[자바] 백준 17271 - 리그 오브 레전설 (Small) (boj java) 문제 : boj17271 다음의 dp식을 사용하면 구할 수 있다. dp[0] = 1로 시작하고, i를 1부터 n까지 증가시키면서 dp[1]부터 dp[n]까지 위의 식을 적용해 계산해주면 된다. dp[i]는 i시간이 있을 때의 경우의 수이다. dp[i-1]은 이전의 경우의 수에 A 기술을 쓰는 경우, dp[i-b]는 이전의 경우의 수에 B 기술을 쓰는 경우를 의미한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final int MOD = 1000000007; private void solu.. 2022. 5. 22.
[자바] 백준 17212 - 달나라 토끼를 위한 구매대금 지불 도우미 (boj java) 문제 : boj17212 N을 1,2,5,7원들을 최소한으로 사용한 합으로 나타내야 하는 문제이다. dp로 쉽게 풀 수 있다. 점화식은 다음과 같다. dp[i]는 i원을 표현하기 위해 필요한 1,2,5,7원 동전의 최소 개수이다. dp[0] = 0을 base condition으로 둔다면 위의 점화식을 통해 N이하의 모든 값에 대해 최소 개수를 구할 수 있다. 답은 dp[n]이 될 것이다. 말로 표현하자면 "i원(dp[i])을 표현하기 위한 최소개수는 i-1원의 최소개수, i-2원의 최소개수, i-5원의 최소개수, i-7원의 최소개수 중 가장 작은 회수에다가 현재의 동전 1개를 추가한(+1) 개수이다." 코드 : github import java.io.BufferedReader; import java.io.. 2022. 5. 20.
[자바] 프로그래머스 - 도둑질 (코딩테스트 연습 Lv4) 문제 : Programmers-도둑질 레벨 4라 보기엔 프로그래머스의 다른 레벨4 문제에 비해 너무 쉽다. DP가 개인적으로 내 최대 약점이라 생각하는데도 금방 점화식이 생각날 정도니 2~3정도가 적당할 것 같다. 레벨4 스킬 체크 딸 때 이거 나왔으면 더 꿀이었을 것 같다. 일단 점화식은 간단하다. dp[i]를 i번 집을 털 때 얻을 수 있는 최대 돈이라 하면 아래와 같이 세울 수 있다. 즉, 현재 i번 집을 털 때 얻을 수 있는 최대 돈은, 이전집을 털고 현재집을 털지 않는것과 이전으로 2번째 집을 털고 이번 집도 터는 것 중 max값을 선택하면 된다. 이렇게 하면 '100 1 1 100' 처럼 중간에 두 집을 건너띄고 털어야 하는 것 까지 한번에 해결된다(세 집을 건너띄는 경우는 없다. 그 경우라면.. 2022. 4. 21.
백준 2602 자바 - 돌다리 건너기 (BOJ 2602 JAVA) 문제 : boj2602 이게 돌다리 2개를 번갈아 건너는 부분을 어떻게 처리할지 감이 잘 안올 수 있어서 그렇지, 그 부분 때고 생각하면 생각보다 어렵지 않다. 1. 그러니 우선 돌다리가 한 줄만 있다고 치고 생각해보자. 이 경우에도 모든 경우를 보기에는 당연히 무리가 있다. 대강 100! (팩토리얼) 정도 나올테니 다 볼순 없다. 브루트포스로 하진 못하겠고, 그럼 돌다리 한 줄만 우선 본다고 했으니 "RRGGSR"에서 "RGS"를 건너면서 지나가는 경우를 생각해보자. 이런건 DP를 사용해 구하면 효율 좋게 구할 수 있다. dp[a][b]를 "RGS"에서 a 인덱스 까지를 표현하는 가지수, b는 "RRGGSR"의 인덱스 라고 정의해보자. 이 경우 다음과 같이 그려볼 수 있다. 최종적으로 가장 우측 아래에.. 2022. 3. 18.
백준 23258 자바 - 밤편지 (BOJ 23258 JAVA) 문제 : boj23258 개인적으로 오늘 푼 플3 문제보다 몇배는 어려웠다. 심지어 플로이드 와샬 알고리즘을 정확히 이해해야 풀 수 있는 문제라고 추천을 받고 풀게되어서 일단 플로이드 와샬을 써야 한다는 점은 알고 풀게 되었는데 그런데도 엄청 해맸다 ㅠ 아무튼 플로이드 와샬을 써보려면 이 문제는 꼭 풀어봐야 할 것 같다. 플로이드 와샬을 이해하는데 도움이 되는 매우 좋은 문제라 생각한다. 1. '2^C 방울 이상 마시면 안된다'의 의미 우선 이 부분부터가 문제였다. 처음엔 뭔가 장난스럽게, 좀 더 복잡하게 보일려고 이렇게 작성했다고 생각했다. 그래서 2^X, 2^C에서 '2^' 부분은 때고 X, C로만 생각했는데 당연히 제대로 답이 안나왔다. 결론적으로 키 아이디어에 해당하는 부분으로 사실 Ce로 가는 .. 2022. 2. 4.
백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3.
백준 15992 자바 - 1, 2, 3 더하기 7 (BOJ 15992 JAVA) 문제 : boj15992 1. 단순화 해서 생각해보기 우선 '사용한 수의 개수는 m개' 라는 조건이 없다고 생각해보자. 이 경우 1부터 n까지의 1차원 DP로 풀 수 있다. dp[a]를 a를 1,2,3을 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 즉, a를 1부터 n까지 증가시키며 다음의 점화식을 적용한 DP를 진행하면 된다. 2. 사용한 수의 개수가 m개 '1'에서 조건이 하나 더 추가되었다. 그러니 2차원 DP로 확장시키면 된다. dp[a][b]를 a를 1,2,3을 b번 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 마찬가지로 a는 1부터 n까지 증가시키면 되고, 이 때 b는 1부터 min(a, m) 까지 증가시키면서 구하면 된다(그냥 b도.. 2022. 2. 2.

티스토리툴바