곽로그

문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 minPrice[n][c] 를 n개의 집을 색칠할때 끝의 집이 c(red, green, blue)인 경우 비용의 최소값으로 정의했다. 따라서 minPrice[n][R] 은 min(minPrice[n-1][G] , minPrice[n-1][B]) + price[n][R]이 된다. 최종 답은 min(minPrice[n][R],minPrice[n][G],minPrice[n][B])이다..

문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static long[] d; public static long MOD = 1000000009; public static void main(String[] args) thr..

문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0부터 n개의 수 k개를 더해서 n을 만든다고 할때 맨 마지막에 더하는 수를 생각해보자. 그 마지막 수에 올 수 있는 수는 0~ n이다. 마지막 수 앞에 오는 수는 0~ (n-마지막수) 중 k-1 개를 더해서 만든 수다. 따라서 f(n,k) 를 0부터 n까지의 수 k개를 더해서 n을 만들 수 있는 경우의 수라고 하면 f(n,k) = f(n-m,k-1) (0

문제 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr check 쉬운문제를 쉽게 풀지못한다 이 문제를 처음에는 자리수를 구하고, N이 그 자리수에서 몇번째 수인지를 구한 다음, 모든 경우의 수를 구해서 해당 번째를 구하려고 했다. 왜 이렇게 복잡하게 생각했냐하면, 진법을 생각하지 못했기 때문 진법! 10진수를 2진수로, 3진수로 변환할 때를 생각해보면, 위 문제는 3진법 012 대신 412가 온거다 0과 0이 아닌 수 진법에서 0의 의미는 자리수가 하나 증가하는 것을 의미한다. 위 문제에서는 0 대신 4가 왔기때문에 윗자리수의 증가가 1번 늦게 시작한다. 즉 012의 3진법의 경우..

문제 [https://www.acmicpc.net/problem/14002] 풀이 소스 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class Main { public static int N; public static int[] numArray; public static int[] longestArr..

문제 https://www.acmicpc.net/problem/10844 풀이 f(n) 을 길이가 n인 계단 수의 갯수라고 하자 그런다음 f(n-1), 즉 길이가 n-1인 계단 수의 갯수와 길이가 n인 계단 수의 갯수가 어떤 관계인지를 생각하자. f(n)은 길이가 n-1 인 계단수의 끝자리에 무엇이 오는 지에 따라 갯수가 정해진다. n-1계단 수의 끝자리가 m이면 n계단 수의 끝자리에 올 수 있는 수는 m-1 또는 m+1 이다. d[n][m]을 길이가 n인 계단 수중에 끝자리가 m인 것의 갯수라고 하면 d[n][m] = d[n-1][m-1] + d[n-1][m+1]이다. 이때 m=1인 경우와 m=9인경우는 따로 처리해주면 된다. 주의사항 d[n][m] = d[n-1][m-1] + d[n-1][m+1]을 ..

문제 www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 처음엔 풀지 못했다가 강의를 듣고 힌트를 얻었다. 이 문제의 핵심은 "같은 수를 두번 이상 연속해서 사용하면 안된다"이다. 이게 어려웠다. f(n)을 1,2,3의 합을 이용해서 나타내는 방법 중 같은 수를 두번이상 사용하지 않은 경우의 수라고 정의해보자. 그런 뒤 f(n)과 f(n-1), f(n-2), f(n-3)과의 관계를 생각해보자 우선 f(n) 과 f(n-1)의 관계를 보면, f(n-1) 은 끝자리가 1, 2, 3 중 하나로 끝나게 된다. 이때 ..

문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 1. 단순재귀 - 입력의 최대가 11이므로 memoization이 없어도 시간초과가 나지않는다. [백준 9095, Java] 1,2,3 더하기 문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io... alwaysbemoon.tistory.com 2. 점화식 - 이..