DP

백준 1010번 다리놓기 [ Java ]

서쪽과 동쪽의 사이트를 연결하는 경우의 수를 구하기 위해선 사이트의 수가 더 많은 곳을 기준으로 잡아야 합니다. 문제에서의 예시로 보면 서쪽엔 4개 동쪽엔 7개의 사이트가 있는데 동쪽의 7개의 사이트 중에 4개를 뽑아야 하니 7C4의 연산이 나옵니다. 조합(Combination)의 연산을 하기 위해 조합의 특징중의 하나인 파스칼의 삼각형을 이용합니다. 파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전 nCr = (n-1)C(r-1) + (n-1)Cr 이므로 이걸 함수로 구현하면 아래와 같이 표현할 수 있습니다. int combination(int n, int r) { if (r == 0 || n == r) return 1; return memo[n][r] = combination(n-1, r-1) + ..

백준 1149번 RGB거리 [ Java ]

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 빨강을 0 초록을 1 파랑을 2라고 생각했을때 N번째가 빨강인 최소비용은 N-1번째가 초록인 최소비용이랑 N-1번째가 파랑인 최소비용중 최솟값 + N번째의 빨강비용입니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..

백준 1915번 가장 큰 정사각형 [ Java ]

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 현재 위치가 1인지 확인하고 1이라면 왼쪽, 위, 왼쪽위 내용들을 검사해서 모두 0이 아니면 최소값 + 1 을 해서 한변의 길이를 구합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[][] map; public static void main(Strin..

백준 9465번 스티커 [ Java ]

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net n번째 스티커를 뜯지 않았을 경우 1번째 줄을 뜯었을 경우 2번째 줄을 뜯었을 경우의 최댓값을 비교한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

백준 2225번 합분해 [ Java ]

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 123더하기에 범위가 추가되었습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); long mod = 1000000000L; int N = Integer.parseInt(st.nextToken(..

백준 1699번 제곱수의 합 [ Java ]

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net D[N]을 모두 1로 채웠을때가 최대기 때문에 D[i] = i(최대값)으로 하고 min 연산을 한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

백준 11659번 구간 합 구하기 4 [ Java ]

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net dp를 사용하여 D[1] 1번째 까지의 합 D[2] 2번째 까지의 합 .. 으로 저장하고 i부터 j까지면 D[j] - D[i]를 하면 맨 첫자리 숫자가 빠지므로 추가적으로 입력받은 + arr[i]를 해줍니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.u..

백준 12852번 1로 만들기 2 [ Java ]

12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이전에 풀었던 1로 만들기 문제dp에 추가적으로 자취를 남길 변수를 사용합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new String..

백준 11057번 오르막 수 [ Java ]

11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int mod = 10007; int N = Integer.parseInt(br.read..

백준 1912번 연속합 [ Java ]

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 현재 수만 사용했을 때와 현재까지 비교한값중 제일 큰 수와 현재수를 더했을때 값을 비교해서 담는다.. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.p..