문제 문제 바로가기> BOJ 17485번: 진우의 달 여행 (Large) 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 풀이 "달 여행에 필요한 최소 연료의 값"을 구하기 위해 모든 경우의 수를 따져보는 경우 O(N^3)이므로, 보자마자 DP로 풀어야 할 거 같은 느낌이 들었다! 나는 우선 각 방향에 번호를 붙여주었다. (k : 0 ~ 2) 다음으로 dp 배열의 의미를 다음과 같이 정의해 주었다. dp[y][x][k] : dp[y][x][k] : 방법 k로 (y, x)에..

문제 문제 바로가기> BOJ 2193번: 이친수 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 dp[N][0] : N자리 수 이찬 수 중 0으로 끝나는 수 dp[N][1] : N자리 수 이찬 수 중 1로 끝나는 수 0으로 끝나는 수는 0과 1이 뒤에 붙을 수 있다. 1로 끝나는 수는 0이 뒤에 붙을 수 있다. 이 점을 이용해서 dp로 문제를 해결했다! #include #define MAX 91 using namespace std; long long dp[MAX][2]; int main() {..

문제 문제 바로가기> BOJ 17404번: RGB거리 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 BOJ 1149번: RGB거리 에 1번집과 N번 집이 연결되어 있다는 조건이 조금 더 붙었다. 따라서 1번 집의 색상을 고정하고, 나머지 집들을 칠하는 방식으로 문제를 해결했다. 1번 집의 색상을 고정한 이유는 마지막 N번 집을 같은 색상으로 칠해주지 않기 위해서다!! (조건문을 통해 처리) #include #define MAX 1002 using namespace std; i..

문제 문제 바로가기> BOJ 12852번: 1로 만들기 2 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 처음엔, 아래와 같이 dp 배열을 구축한 후, 구축된 배열에서 역추적해가며 N을 1로 만드는 방법에 포함되어 있는 수를 출력해주었다. 이 때는 ,, dp[1] = 0을 1로 초기화 해줘서 앞에서 리턴하게 하고 암튼 그랬지만, 전반적인 역추적 아이디어는 아래와 같았다. 그런데 사실 dp 배열을 만드는 과정에서 배열을 하나 더 만들어서 그 이전 값을 저장하는 dp 배열을 만든다면??!! 더 편하게 "N을 1로 만드는 방법에 포함되어 있는 수"를 구할 수 있다!! dp 배열이 업데이트 됨에 따라 그 값을 담고 ..

문제 문제 바로가기> BOJ 16974번: 레벨 햄버거 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 풀이 패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다. N 0 1 2 3 4 5 ... patty 1 3 7 15 31 63 ... 햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다. (재귀적으로, 분할정복으로 해결하기 위해) 1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우 : get_patty(n-1, x-1) = 레벨을 낮추어 재귀적으로 탐색해준다. x-1..

문제 문제 바로가기> BOJ 11053번: 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP와 이중 for문을 이용해 "현재 수를 마지막으로 하는 가장 긴 증가하는 부분 수열"의 길이를 저장해주었다. 이렇게 저장해두면, 답은 dp 배열 중 가장 큰 값이 되고, 이를 반복문을 돌 때 함께 업데이트 해주면 된다! #include #define MAX 1001 using namespace std; in..

문제 문제 바로가기> BOJ 2098번: 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 중요한 Point 1. 출발지가 어디든 그 결과는 같다. A → B → C → A B → C → A → B C → A → B → C 조금만 들여다보면, 순회하기 때문에, 어느 지점에서 출발하든 동일한 경로가 되는 것을 확인할 수 있다. 따라서 출발지를 고정 시킨 후 탐색을 진행한다! 2. 중복되는 경로가 생긴다. 이미 방문해서 최소값을 찾아 놓은 부분 경로의 경우, ..

문제 문제 바로가기> BOJ 14501번: 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 dp를 이용해서, 뒤에서부터 거꾸로 오면서, 백준이가 얻을 수 있는 최대 수익을 구해 줄 수 있다. `dp[i]` : i+1 ~ N일 기간, 백준이가 얻을 수 있는 최대 수익 #include #include #define MAX 16 using namespace std; int N; int dp[MAX]; pair consult[MAX]; // time, pay void input(){ cin >> N; int t, p; for(int i=0; i> t >> p; consult[i] = {t, p}; } } void solution(){ for(i..

문제 문제 바로가기> BOJ 11057번: 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 아래와 같은 규칙을 가지므로, 점화식이 dp[i][j] = (dp[i][j-1] + dp[i-1][j])%DIV 이다! #include #define MAX 1001 #define DIV 10007 using namespace std; int N; int dp[MAX][11]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0)..

문제 문제 바로가기> BOJ 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수 1. j == coin[i] 인 경우, 동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1 2. j > coin[i] 인 경우, 해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1) #include #define INF 9876543..

문제 문제 바로가기> BOJ 2293번: 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열로 풀면 메모리 초과가 발생하므로 1차원 배열로 풀어야 한다. i원 동전을 사용하여 j원을 만들 때 j-coin[i]의 누적합만 알면 되므로 1차원 배열로 풀 수 있다. #include #define MAX 101 #define MAX_K 10001 using namespace std; int n, k; int coin[MAX], dp[MAX_K]; void input(){ cin >> n >> k..

문제 문제 바로가기> BOJ 9465번: 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 다이나믹을 이용해서 푸는 문제였다. dp[i][j-1] + dp[1][j]가 dp[2][j] 보다 작은 경우 dp[1][j-2] + dp[2][j]를 해주는 것이 최대값이 된다. 이를 i가 1인 경우와 2인 경우로 나누어 각각의 위치에서 스티커의 점수를 더하여 얻을 수 있는 최대값을 구해주었다! #include #define MAX 100001 using namespace std; int N; in..

문제 문제 바로가기> BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 주어진 조건을 만족하면서 다음 계단에 도착하는 방법은 다음과 같이 총 2가지이다. 1. 두 계단 전에서 현재 계단으로 : dp[i-2]+arr[i] 2. 한 계단 전에서 현재 계단으로 : dp[i-3]+arr[i-1]+arr[i] 따라서 위 점화식을 토대로 max 값을 찾아내면 된다! #include #define MAX 301 using namespace std; int N; int arr[MAX], dp[MAX]..

문제 문제 바로가기> BOJ 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 풀이 0-1 knapsack 문제로, 다이나믹 프로그래밍을 이용하여 해결할 수 있다. dp[i][j] : i개의 물건을 가지고, 최대 무게가 j 일 때 담을 수 있는 최대 가치 #include #define MAX 101 #define MAX_K 100001 using namespace std; int N, K; int weight[MAX], ..