ohsopp's coding

문제

문제 해결

문제에서 K번 작업의 선행 작업들의 번호는 모두 1이상 K-1 이하라는 조건이 주어졌으므로 dynamic programming 기법을 사용할 수 있습니다. 해결 알고리즘은 간단합니다. K번 작업의 선행 작업들 중 가장 마지막까지 수행된 작업의 시간에 K번의 작업시간을 더해줍니다.

각 작업이 걸리는 시간을 저장하는 배열을 arr_time[],

dp[i]에 i번 작업이 완료되는 데 걸리는 최소 시간,

task[i][]에 i번 작업의 선행 작업

을 저장하겠습니다.

한 가지 주의사항이 있습니다. 문제를 잘 읽어보면 선행 작업이 없는 작업은 최소 한 개 이상이며 1번이 그러하다고 적혀있습니다. r을 i번의 선행 작업 번호라고 한다면, dp[i] = max(dp[i], dp[r] + arr_time[i]) 처럼 작성하면 선행 작업이 없는 작업일 때는 이 명령을 수행하지 않으므로 엉뚱한 결과가 나올 수 있습니다. 

다음과 같은 입력이 주어졌다고 가정하겠습니다.

5

5 0

3 1 1

3 1 2

3 1 3

100 0

위 상황은 5개의 작업 중 1번부터 4번까지는 (1 - 2 - 3 - 4)로 연쇄적이고, 5번은 독립적입니다.

dp[i] = max(dp[i], dp[r] + arr_time[i])로 수행한 결과는 잘못된 값인 14가 나옵니다. 이유는 마지막 입력인 5번 작업은 선행 작업이 없으므로 max 문장이 수행되지 않기 때문입니다. 옳은 결과인 100을 출력하려면 선행 작업이 없는 경우를 대비하여, 선행 작업의 시간이 0 또한 가능하게 만들어줍니다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m, ans, arr_time[10001], dp[10001];
vector<int> task[10001];

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> arr_time[i] >> m;

		while (m--) {
			int pretask;
			cin >> pretask;
			task[i].push_back(pretask);
		}
	}

	dp[1] = arr_time[1];

	for (int i = 2; i <= n; i++) {
		int max_pretask = 0;

		for (auto r : task[i])
			max_pretask = max(max_pretask, dp[r]);

		dp[i] = max_pretask + arr_time[i];

		ans = max(ans, dp[i]);
	}

	cout << ans;
}

문제

문제 해결

문제에서 주어진 각 연산에서 필요로 하는 조건 설정에 유의해야 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

→ 화면에 출력된 이모티콘의 개수가 1개 이상이어야 한다.

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

→ 클립보드에 저장된 이모티콘의 개수가 1개 이상이어야 한다.

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

→ 화면에 출력된 이모티콘의 개수가 1개 이상이어야 한다.

실행시간 단축을 위해 bool형 2차원 배열 visit을 선언하여 관리한다. visit[i][j]에는 현재 화면에 보여지는 이모티콘의 개수가 i개, 클립보드에 저장된 이모티콘의 개수가 j개일 때 해당 상황을 방문한 적이 있는지 저장한다.

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 2000
queue<pair<int, int>> q;
queue<int> c;
int s;
bool visit[MAX][MAX];

int bfs() {
	visit[1][0] = 1;
	q.push({ 1,0 });
	c.push(0);

	while (!q.empty()) {
		int disp = q.front().first, clip = q.front().second;
		int cnt = c.front();
		q.pop(); c.pop();

		if (disp == s) return cnt;

		if (disp > 0 && disp <MAX) {

			// 1. 화면에 있는 이모티콘을 모두 클립보드로 복사하는 연산
			if (!visit[disp][disp]) {
				visit[disp][disp] = 1;
				q.push({ disp, disp });
				c.push(cnt + 1);
			}

			// 3. 화면에 있는 이모티콘 중 하나를 삭제하는 연산
			if (!visit[disp - 1][clip]) {
				visit[disp - 1][clip] = 1;
				q.push({ disp - 1, clip });
				c.push(cnt + 1);
			}
		}

		// 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣는 연산
		if (clip && disp + clip < MAX) {
			if (!visit[disp + clip][clip]) {
				visit[disp + clip][clip] = 1;
				q.push({ disp + clip,clip });
				c.push(cnt + 1);
			}
		}
	}

	return 0;
}

int main() {
	cin >> s;

	cout << bfs();
}

문제

문제 해결

문제에서 한 가지 조건에 주의해야 한다. 구하는 값은, 모든 곡 중 최대 볼륨이 아니라 마지막 곡의 최대 볼륨이다.

dp[i][j]가 1이면 i번의 곡까지 재생할 때 가능한 볼륨 j를 의미한다.

1 ≤ N ≤ 50, 1 ≤ M ≤ 1000 이므로 dp[51][1001]로 선언한다.

시작 볼륨 S를 dp[0][S] = 1로 설정하기 위해 곡의 인덱스를 1부터 시작한다.

코드

#include <iostream>
using namespace std;

int chk, res, N, S, M, a[52];
bool dp[51][1001];

int main() {
	cin >> N >> S >> M;

	for (int i = 1; i <= N; i++) cin >> a[i];
	
	dp[0][S] = 1;

	for (int i = 0; i < N; i++)
		for (int j = 0; j <= M; j++)
			if (dp[i][j]) {
				if (j + a[i + 1] <= M) dp[i + 1][j + a[i + 1]] = 1;
				if (j - a[i + 1] >= 0) dp[i + 1][j - a[i + 1]] = 1;
			}
	
	chk = -1;

	for (int i = M; i >= 0; i--)
		if (dp[N][i]) {
			chk = i;
			break;
		}

	cout << chk;
}

문제

문제 해결

dp와 메모이제이션 기법을 이용하여 풀 수 있는 문제다.

이 문제의 알고리즘은 "백준 12865 : 평범한 배낭"  과 비슷하다. 백준의 12865 평범한 배낭에서 dp[i][j]는 i번까지의 물건 중, 담은 무게 j에 올 수 있는 최대 가치 합을 나타냈다.

이 문제에서 최대 N은 100, 최대 M은 10,000,000이나 되므로 dp[101][10,000,001]의 배열을 생성할 수 없다.

그러나 각 앱을 비활성화하기 위한 비용은 최대 100까지밖에 들지 않는다. 따라서 최대 100개 앱의 비활성 비용은 아무리 많아도 10,000 이하라는 것을 알 수 있다.

dp[i][j]의 의미를 바꾸어 i번까지의 앱 중, 비활성 비용 j만큼 사용하여 가능한 최대 메모리로 정의하겠다. 그렇다면 dp[101][10,001]의 크기만큼만 할당하여 관리할 수 있다.

(+ 전에 배낭 문제를 풀어봤는데도 문제 푸는데 생각보다 오래 걸렸다. 한 번 풀었다고 넘어가지 말고 문제 스크랩해가면서 여러 번 다시 봐야겠다.)

코드

#include <iostream>
using namespace std;

int N, M, m[101], c[101], dp[101][10001];

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) scanf("%d", m + i);
	for (int i = 1; i <= N; i++) scanf("%d", c + i);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 10000; j++) {
			if (j < c[i])
            	dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i]);
		}
	}

	int t = 1;
	for (; t <= 10000; t++) if (dp[N][t] >= M) break;

	cout << t;
}

문제

문제 해결

다이나믹 프로그래밍 기법을 사용하여 풀 수 있는 문제다.

문제 풀이의 알고리즘을 떠올리는게 쉽진 않았지만 떠올리기만 한다면 코드 구현은 매우 쉽다.

​

​

해결 방법 :

배열 dp[N][K]는 N번째 항까지 계산이 완료된 식의 결과값을 K라고 할 때, 가능한 등식의 개수를 의미한다.

​

초기값 dp[1][a[1]]을 1로 설정해야 한다. 첫 번째 항에서 가능한 등식의 개수는 1개 뿐이기 때문이다.

​

입력의 마지막 항은 계산하지 않는 등호의 우변이므로 K가 입력의 마지막 항이 되고, 계산은 N-1번째까지 하면 된다.

입력을 a[]배열에 저장하고 a[1]부터 a[n]까지 n개의 입력이 주어진다고 가정하자.

​

n-1번째까지 계산한 결과값이 마지막 항(a[n])이 되는 등식의 개수 구해야하므로,

최종적으로 구하고자 하는 값은 dp[n-1][a[n]]이 된다.

코드

#include <iostream>
using namespace std;

int n, a[101];
long long dp[101][21];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)  // a[1]부터 시작
        cin >> a[i];

    dp[1][a[1]] = 1;

    for (int i = 2; i < n; i++)
        for (int j = 0; j <= 20; j++)
            if (dp[i - 1][j]) { // 이전 항 계산 결과의 0 ~ 20 중에 계산된 적이 있는 숫자가 있을 때

                if (j + a[i] <=20) // i 번째 항과의 덧셈이 20 이하인 경우
                    dp[i][j + a[i]] += dp[i - 1][j];

                if (j - a[i] >= 0) // i 번째 항과의 뺄셈이 0 이상인 경우
                    dp[i][j - a[i]] += dp[i - 1][j];
            }

    cout << dp[n - 1][a[n]];
}

문제

문제 해결

LIS(Longest Incresing Subsequence, 최장 증가 부분 수열)을 이용한 문제다.

​

​

문제의 알고리즘은 다음과 같다.

​

1부터 N까지 오름차순으로 세우되 가장 적게 이동하여야 한다. 따라서 이미 오름차순으로 정렬되어있는 부분 수열들 중, 가장 긴 것을 선택하여 그 길이를 N에서 빼면 문제에서 원하는 값이 나온다.

​

주의사항 : 나올 수 있는 최소 부분 수열의 길이는 1이므로 dp[0]에 0을 대입하고 dp[1]부터 시작하여야 한다.

예를 들어 입력이 5 4 3 2 1인 경우, dp[1]부터 dp[5]까지는 모두 1의 값을 갖는다.

이는 각 인덱스가 dp[1]이 아닌 dp[0](항상 0)부터 비교해야 나올 수 있다.

​

코드

#include <iostream>
using namespace std;

int n, m, a[202], dp[202];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + 1);

    for (int i = 1; i <= n; i++) m = max(m, dp[i]);

    cout << n - m;
}