취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3286번 문제인 SHELVES이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3286 

같은 열의 두 높이 h1 < h2에 대하여, h2의 높이에 물건을 집을 수 있다면 h1의 높이에 있는 물건 또한 집을 수 있음을 관찰할 수 있다. 따라서 같은 열에 물건이 여럿 있다면 더 높은 위치에 있는 물건만을 고려해 문제를 풀어도 충분하다. 그러므로 이제부터는 각 열마다 접근해야 하는 가장 높은 위치(없다면 0)만을 고려해 문제를 해결하도록 하자.

dp[r][c]를 "c열에서 높이 r까지 접근 가능한 사다리를 설치한 경우, c열 이하의 모든 열의 꺼내야 할 물건을 모두 꺼내기 위한 최소비용"으로 정의하자.

이 dp[r][c]의 값은 (1) c열에 설치한 높이 r의 사다리가 c열에 있는 물건에 접근할 수 있는지, 접근할 수 있다면 (2) c-1열에 있는 물건 또한 접근할 수 있는지의 여부에 따라 c-1, c-2열의 dp값을 이용해 계산해낼 수 있음을 관찰할 수 있다.

위 관찰을 이용해 dp[r][c]의 값을 구해내는 점화식을 찾아 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C, N;
int col[102];
int dp[101][102];

int ans = 1000000007;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> C >> R >> N; C++;
	while (N--) {
		int A, B; cin >> A >> B; A++;
		col[A] = max(col[A], B);
	}

	for (int r = 0; r <= R; r++) {
		dp[r][0] = dp[r][1] = r;
		for (int c = 2; c <= C; c++) {
			dp[r][c] = 1000000007;
		}
	}

	//dp[r][c] : c열에 r짜리 막대를 놓은 상황. 이 때 c열까지를 완전히 채울 때의 최솟값
	for (int c = 1; c <= C; c++) {
		for (int r = 0; r <= R; r++) {
			if (r < col[c]) {
				for (int rr = col[c]; rr <= R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
				}
			}
			// 아래는 이제 r>=col[c] 성립
			else if (r < col[c - 1]) {
				for (int rr = 0; rr <= R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
				}
			}
			else {
				for (int rr = 0; rr < R; rr++) {
					dp[r][c] = min(dp[r][c], dp[rr][c - 2] + r);
				}
			}
		}
	}

	for (int r = 0; r <= R; r++) ans = min(ans, dp[r][C]);

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3287번 문제인 CALC이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3287 

이 글에서 op는 연산자 문자('#' 또는 '$')를 의미하고, X와 Y는 표현식을 나타내는 문자로 사용하겠다.

주어지는 표현식은 "A", "B"를 제외하면 항상 "(ext op exp)"와 같은 형태로 구성되어 있음을 관찰하자.

위의 관찰을 이용하면, 다음과 같은 세 가지를 할 수 있다면 문제를 충분히 해결할 수 있음을 발견할 수 있다.

(1) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 A A B로 교체하기

(2) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 B A B로 교체하기

(3) 리스트의 끝이 X Y A B와 같이 주어져있을 때 그 위치의 리스트를 (X op Y) A B로 교체하기

위 세 가지를 하는 방법의 자세한 설명은 생략하도록 하겠다. 다만 아래의 코드에 가능한 방법중 하나가 나와있으므로 전혀 방법을 못 찾겠다면 참고해보자.

위의 세가지가 가능하다면, 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 X A B로 교체하는 함수 f(X)를 고안해낼 수 있다. 구체적으로 X가 A와 같다면 (1)을, B와 같다면 (2)를, (P op Q)와 같다면 f(P), f(Q) 및 (3)을 순서대로 호출하는 것으로 리스트의 끝이 A B와 같을 때 이를 X A B로 바꿀 수 있다.

이와 같은 함수 f를 이용해 A B를 exp A B로 바꾸고, DROP을 2회 실행해 문제를 해결하자.

위와 같은 방법이 문제의 제약(리스트의 원소의 최대개수가 100, 총 1만번의 연산만 수행 가능)을 만족하는지를 확인하는 것은 간단하므로 서술을 생략한다.

아래는 제출한 소스코드이다.

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

string s;

void func(int L, int R) {
	if (L == R) {
		if (s[L] == 'A') {
			cout << "SWAP\n";
			cout << "DUP\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
		}
		else {
			cout << "DUP\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
		}
		return;
	}
	int cnt = 0;
	L++, R--;
	for (int i = L; i <= R; i++) {
		if (s[i] == '(') cnt++;
		else if (s[i] == ')') cnt--;
		else if ((s[i] == '#' || s[i] == '$') && !cnt) {
			func(L, i - 1);
			func(i + 1, R);
			cout << "ROT\n";
			cout << "ROT\n";
			if (s[i] == '#') cout << "HASH\n";
			else cout << "DOLLAR\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	func(0, s.length() - 1);
	cout << "DROP\n";
	cout << "DROP\n";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3285번 문제인 DECODE이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3285 

주어진 규칙에 따라 문자의 대응규칙을 나타내는 표를 만들어 문제를 해결해주자.

'A'부터 'Z'까지의 문자가 아스키코드에서 연속한 정수에 할당되어있음을 이용하고, 키워드에서 사용한 문자가 무엇인지를 기록하는 배열을 만들어둔다면 아래와 같이 대응규칙 표를 간단히 만들 수 있다.

아래는 제출한 소스코드이다.

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

char table[128];
bool visited[128];

string kword, s;
int idx;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> kword >> idx;
	idx--;
	for (auto& l : kword) {
		visited[l] = 1;
		table[l] = idx + 'A';
		idx++;
		if (idx == 26) idx = 0;
	}
	for (char c = 'A'; c <= 'Z'; c++) {
		if (visited[c]) continue;
		table[c] = idx + 'A';
		idx++;
		if (idx == 26) idx = 0;
	}

	cin >> s;
	for (auto& l : s) cout << table[l];
}