끼루루룩

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 설명 dp[i-1] + arr[i] 와 arr[i] 를 비교했을 때, arr[i]값이 더 크면 이 전에 더해왔던 연속합들을 버리고 다시 i부터 시작하면 된다. dp[n]이 아니라 중간에서 최댓값이 나올 수 있기 때문에 max를 두어 dp[i]의 최댓값을 삽입! 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReader; imp..

1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 설명 반례를 생각못해서 틀렸었다. 연속해서 3잔을 못마신다는 의미에서 저번에 푼 계단 오르기(백준-2579) 문제랑 비슷했다. 따라서 식 구하는 것도 비슷하게 구하면 된다. 하지만 저번 문제와 다른점으로 이 문제에선 포도주를 연속해서 2번이상 안마실 수 있다. 따라서 이 반례를 고려해서 dp[n]을 구할 때 dp[n-1]과 비교하여 큰 값을 넣어줬다. 3. 코드 import java..

1. 문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 2. 설명 손으로 계산해서 점화식을 얻으니까 피보나치랑 같았다. 그렇게 dp배열해서 정답 제출하니까 틀리더라? ?? int 배열이 피보나치 감당할 수 있는 범위가 42?정도 까지 였던거 같다. 따라서 long 타입으로 선언해야 된다. 3. 코드 import java.util.Scanner; public class Main { public static void main(Stri..

1. 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 설명 dp배열 초기화 때문에 헤맨 문제 무조건 첫번 째 계단부터 시작해야 되는 줄 알았는데 그런 조건은 없다. 마지막 계단만 밟으면 됨. 따라서 dp[2]에 첫번 째 계단, 두번 째 계단을 밟을 경우와 첫번 째 계단, 세번 째 계단을 밟을 경우 중 최댓값을 삽입해야 한다. 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReade..

1. 문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 설명 N을 기준으로 N-1이 R일 경우, G일 경우, B일 경우를 모두 고려해서 최솟값을 구해야한다. (두 번째 for문) 그렇게 dp배열에 저장하고, 그 중 최솟값이 비용의 최솟값이 된다. 1번집부터 시작하기 때문에 배열의 크기는 N+1로 잡았다. 3. 코드 import java.util.StringTokenizer; import java.io.Buffere..

1. 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 설명 피보나치랑 같다! 3. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] dp = new int[1001]; dp[1] = 1; dp[2] = 2; for(int i..

1. 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 2. 설명 피보나치인데 조금 다른? 문제! 0의 수랑 1의 수를 계산해서 출력하는 문제인데, 출력하는 부분이 다를 뿐 기본적으로 피보나치랑 같다. 피보나치 결과를 저장하지 않고 각각 호출하는 0과 1의 수를 저장해두고 출력했다. n의 최댓값이 40이라서 함수 크기는 41, 2는 0과 1을 저장해야 되므로 2로 잡았다. 3. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { ..

1. 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 2. 설명 DP로 접근했을 때, n=4 일 때 경우의 수가 1 + 3 (1의 경우의 수 + 3) 2 + 2 (2의 경우의 수 + 2) 3 + 1 (3의 경우의 수 + 1) n=5 일 때 경우의 수가 1 + 4 (1의 경우의 수 + 4) 2 + 3 (2의 경우의 수 + 3) 3 + 2 (3의 경우의 수 + 2) 4 +..