문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 - 입력의 경우 int 배열로 100개까지 받으므로 400byte - 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음 - 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리 시간 복잡도 상향식 (Bottom-Up) 하향식(Top-Down, 재귀 함수) O(N * 20) O(2^n) = O(2^100) - ..

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 - 시간복잡도 : O(N) - 점화식 DP[N] = DP[N - 2] + DP[N - 1] 형태로 최대 N이 90까지 가능하다 - 피보나치의 경우 46번째만 넘어가도 29억이 넘기 때문에 long (8byte, 64bit)으로 문제 풀이 해야 함 풀이 순서 가짜 문제 정의 - 가짜 문제로 정답을 구할 수 있는가? - 초기항 - 점화식 - 풀이 & 테스트 0 1 2 ..

문제 링크 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N) - 메모리 제한 4MB 직접 문제를 풀었을 때 최대 값을 구하는 것은 Bottom-Up방식으로 설명에 따라 그대로 하였기에 구할 수 있었다. 그러나 최소 값의 경우 구할 수 없었고, 기술 블로그를 찾아 본 결과 '메모리 제한', '슬라이딩 윈도우 기법'와 같은 파악하지 못 한 부분에 대해서도 확인할 수 있었다. (최소값의 경우 반대로 선택 가능 범위 내에 최소 값을..

문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다. 2차원 배열 DP로 풀이시 문제가 되었던게 '0 ~ 9의 숫자를 사용한 여부는 어떻게 알 수 있을까' 였습니다. 3차원으로 변경하여 0 ~ 9 까지 체크했는지 반복문으로 사용해서 할 경우 그거대로 더 복잡해 질거 같은 생각이 들었습니다. 기술 블로그를 찾아본 결과 해당 문제는 '비트 마스킹' 기법을 사용하여 문제 풀이 가능한 것을 알게 되었고 2~3일간 이해가 되지 않아 시간을 보냈고, 지금은 이해한 내용을 ..

문제 링크 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 0) { T -= 1; N = Integer.parseInt(br.readLine()); sb.append(sumValue(N)).append("\n"); } } static long sumValue(int n) { long result = 0L; for(long v : DP[N]) { result += v; } return result; } static void preProcess() { DP = new long[65][10]; for(int i = 0; i

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N), 최대치 Integer 범위 내 - 스티커 하나를 뜯을 경우 상하좌우로 찢어져서 사용할 수 없게 됨 - 2 x N열 스티커, 2차원 배열 형태의 DP 문제 초기화 1 DP[0][i] 50 DP[1][i] 30 0번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨 0 1 2 O 스티커 선택 O O 1번행의 2열..

문제 링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - DP 상향식 문제 *절차 (1) 가짜 문제 정의 진짜 문제 = 주어진 N에 대해 N을 1,2,3의 합으로 표현하는 경우의 수 가짜 문제 = DP[i] 를 1,2,3으로 표현하는 경우의 수 (2) 가짜 문제를 풀면 진짜 문제를 풀 수 있는가 ? YES (3) 초기항 정의 0 1 2 3 0 1 2 ( 1 + 1, 2) 4 - 0에 3을 더할 경우 - 1에 2를 더할 경우 - 2에 1을 더할 경우 (4) 점화식 세우기 DP[i] = DP[i - 1] +..

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 - 시간 제한 0.5초 이므로 완전 탐색으로 풀 경우 시간 초과 발생 - 첫번째 집의 RGB 값으로 초기값을 설정하고, 동적 프로그래밍으로 풀이한다 - 최종적으로 DP[N][1 ~ 3] 값 중 최소값 출력 - 시간복잡도 : O(N) 점화식 DP[i][j] = Math.min(DP[i - 1][x], DP[i - 1][y]) + RGB[i][j] (이때 i..

문제 링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^2) - "병사 배치하기" 문제에서 역추적을 추가한 문제 - Stack의 성질(LIFO)을 활용하게 되면 pop하는 것만으로도 오름차순 정렬 결과를 구할 수 있다 https://dev-ljw1126.tistory.com/271 [BOJ 18353] 병사 배치하기 (Ja..

문제 링크 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 - DP, LIS (Longest Incresing Subsequence, 최장 증가 부분 수열) - 시간 복잡도 O(N^2) - 단순히 LIS 최대 길이를 구한 후 N과 차이를 구하면 되는 문제라서 DP 배열을 순차적으로 갱신 해준다 (1) 입력된 배열을 reverse함 (2) DP 배열을 1로 초기화함 (숫자 자신을 가르킴) (3) 순차 조회하면서 앞에 숫자 중..

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N * 10) = O(N) - MOD를 나누지 않으면 터지는 이유 확인 필요 DP[i][j] = i 는 자리수 이고, j는 j로 끝나는 수를 뜻함 i\j 0 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 2 10 21 12, 32 23, 43 34, 54 45, 65 56, 76 67, 87 78, 98 89 제출 코드 1) Bottom-Up 방식 import java.util.*; import java.io.*; public class Ma..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 - 상향식(Bottom-up)으로 DP 풀이 - 시간복잡도 O(N) *DP 배열 결과 idx 0 1 2 3 4 5 6 7 8 9 10 DP 0 0 1 1 2 3 2 3 3 2 3 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] DP; static void input() throws Exception { BufferedReader br = new BufferedReader(new..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net문제 풀이 - 시간복잡도 O(N)- 초기항 구하고, N번째 포도주에 대해 아래 3가지 경우를 비교하여 최대 값 구함  이때 3번 연달아 포도주를 마실 수 없다는 규칙에 따라 DP 테이블을 갱신한다 i번째 포도주를 마시지 않는 경우① DP[i - 1]할당 i번째 포도주를 마시는 경우② i - 1 번째 포도주 먹고 마시는 경우 최대치 (DATA[i - 1] + DP[i - 3])③ i - 2 번째..

문제 링크 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 풀이 - DP, 피보나치(fibonacci) 응용하여 풀면되는 문제였음 - 시간 복잡도 O(N * M) 절차 (1) DP 배열에 좌석 개수별 경우의 수를 미리 구함 (2) 앉을 수 있는 좌석 범위를 각각 구한 후 곱셈 연산으로 결과값 구함 (이때 모든 좌석이 VIP인 경우 앉을 수 있는 경우의 수는 1) *DP 초기항 구할 경우 자리가 1개 일 때 1가지 경우의 수 자리가 2개 일 때 2가지의..

문제 링크 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - DP 배열의 경우 이전 값과 곱한 경우와 자기 자신과 비교했을 때 더 큰 값을 갱신 1 2 3 4 5 1.1 0.7 1.3 0.9 1.4 1.1 0.77 1.3 1.117 1.638 *참고. 자바 소수점 처리 https://bullie.tistory.com/7 [Java] 자바 소수점 원하는 자리수 만큼 출력 자바로 문제를 풀다보면 소수..

문제 링크 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 - 00, 1 이 주어지고, N 자리 수 만큼의 2진 수열 개수를 구하는 문제 - N = 1,000,000 인 경우 int[] DP = new int[N + 1] 했을 때 배열 자리수 하나당 4byte 차지하므로 4MB 용량 차지 (제한 256MB) - 상향식 방식으로 풀이하여 O(N) 시간복잡도 소요됨 초기화 DP 0 1 2 ... 0 1 2 ... N = 1 의 경우 1 N =..

문제 링크 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 - 매 테스트 케이스마다 피보나치 함수로 구할 경우 '시간 초과' 에러 발생 - fibo(N) = fibo(N - 1) + fibo(N - 2) 형태로 구해지는 피보나치 수열은 재귀 방식으로 구할 때 O(2^n) 시간복잡도 가짐 (N이 최대 40일 때 2^40은 대략 10^12) 그래서 - 상향식으로 40번째 배열 까지 DP 배열에 값을 구한 후 호출하게 되면 O(N) 시간복잡도로 구해짐 이때 0, 1 초기항 처리 후 호출 0 1 2 3 4 5 0 1 1 2 3 4 특이한..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 - 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름) - '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음 점화식 - 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함 - 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] - 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자..