알고리즘/백준 풀이(동적 프로그래밍)

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단 수는 0으로 시작하면 안되며 인접한 숫자마다 1의 차이를 가져야한다. 따라서 아래 그림과 같이 경우의 수를 나열해볼 수 있다. 여기서 N=3 일 때 뒤 2자리는 N=2 인 경우에서 가져온다는 규칙을 알 수 있다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다음 문제는 확통에서 배운 nCr 을 사용하면 풀린다. 여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다. 여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다. 코드 import java.io.*; import java.util.*; public class Main { static int[][] dp = new int[30][30]; ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 다음 문제는 피보나치 수열을 이용하여 풀 수 있었다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long dp[] = new long[101]; long arr..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 위의 예제를 바탕으로 풀어보면 다음과 같다. 맨 처음 dp[0] 값은 1로 설정하고 arr[1] 의 값이 arr[0] 보다 크면 dp[1] 의 값은 dp[0] 에 1을 더한 2로 설정한다. arr[2] 의 값이 arr[0] , arr[1] 보다 크지 않기 때문에 dp[2] 의 값은 1로 설정한다. arr[3] 의 값이 ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다음 문제는 경우의 수를 모두 작성하여 규칙을 본 결과 피보나치 배열과 같다는 걸 알게 되었다. N자리 이친수의 개수는 다음과 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이 문제는 계단 오르기 방식과 비슷한 형태의 문제이다. https://3946.tistory.com/94 백준 2579번 - 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는 3946.tistory.com 먼..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다음 문제를 푸는 방식은 다음과 같다. 다음 예제처럼 수열이 존재할 때 왼쪽부터 수를 비교하여 연속되는 수의 합의 모든 경우의 수를 dp 라는 배열 안에 삽입한 뒤 dp 배열 중 최댓값을 찾으면 된다. 10 > -4 이기 때문에 두 수를 더한 6을 dp[1]에 저장 10+(-4) > 3 이기 때문에 세 개의 수를 더한 9를 dp[2]에 저장 10+(-4)+3 > 1 이기 때문에 네 개의 수를 더한 10을 d..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 각 층마다의 최솟값을 구하여 더하는 게 아니라 모든 경로의 경우의 수를 구하여 그 값 중 최솟값을 찾아야한다. 결과적으로 마지막에 RGB 중 R을 선택하는 경우, G를 선택하는 경우, B를 선택하는 경우 중 가장 최솟값을 찾아야한다. https://st-lab.tistory.com/128 다음 블로그를 참고하여 쉽게 이해할 수 있었다. [백준] 1149번 : RGB..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 다음 피보나치 문제는 풀이는 되지만 시간초과 때문에 애를 많이 먹었던 것 같다. 그리하여 Scanner 대신 BufferedReader 와 BufferedWriter를 사용하였다.(시간 면에서 다음과 같은 차이를 보인다.) 입력 방식 수행시간(초) java.util.Scanner 6.068 java.io.BufferedReader 0.934 count_0은 0의 갯수, count_1은 1의 갯수를 나타낸다. 코드 import java.io.*; import java.util.*; public ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net