취미로 코딩하기

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

이번에 볼 문제는 백준 2116번 문제인 주사위 쌓기이다.
문제는 아래 링크를 확인하자.

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

맨 아래의 주사위의 밑면을 하나 고정한다면, 쌓은 주사위의 각 층에 사용될 수 있는 옆면의 수는 네 종류로 전부 고정됨을 관찰하자. 이 관찰을 이용하면 각 주사위의 밑면을 고정하는 여섯 경우에 대한 탐색을 통해 문제를 간단히 해결할 수 있다.

이를 구현하는 것은 어렵지 않다. (1) 밑면에 있던 수를 마주보는 면에 있는 수로 바꾸고 (2) 앞에서 나온 두 수를 제외한 수 중 최댓값을 더하는 두 작업을 반복하는 코드를 작성하는 것으로 구현할 수 있기 때문이다.

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

#include <iostream>
using namespace std;

int N;
int psum[6];
int uface[6] = { 1,2,3,4,5,6 };

int mx;

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

	cin >> N;
	while (N--) {
		int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
		for (int i = 0; i < 6; i++) {
			int& cur = uface[i];
			if (cur == a) cur = f, psum[i] += max(max(b, c), max(d, e));
			else if (cur == b) cur = d, psum[i] += max(max(a, c), max(e, f));
			else if (cur == c) cur = e, psum[i] += max(max(a, b), max(d, f));
			else if (cur == d) cur = b, psum[i] += max(max(a, c), max(e, f));
			else if (cur == e) cur = c, psum[i] += max(max(a, b), max(d, f));
			else cur = a, psum[i] += max(max(b, c), max(d, e));
		}
	}

	for (int i = 0; i < 6; i++) mx = max(mx, psum[i]);

	cout << mx;
}

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

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

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

오목 게임의 한 장면이 주어질 때, 승패가 결정났는지를 먼저 판단하고, 결정났다면 연속으로 다섯개 놓여있는 돌의 위치가 어디인지를 추가로 출력하는 문제이다.

바둑판 위에서 일렬로 다섯 개의 돌이 연속으로 위에 놓일 수 있는 모든 가능한 방법에 대해 (1) 해당 다섯 위치에 같은 돌이 올려져 있고, (2) 그 연장선에 해당하는 위치에 그 같은 돌이 올려져있지 않은지를 확인해 승패가 결정났는지를 판단할 수 있다.

돌이 다섯 개 연속으로 놓인 곳의 위치를 출력할 때, 가장 위쪽에 놓인 돌이 우선순위가 아닌 가장 왼쪽에 놓인 돌의 위치를 우선적으로 출력해야함에 유의하자.

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

#include <iostream>
using namespace std;

int board[21][21];

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

	for (int r = 1; r < 20; r++) {
		for (int c = 1; c < 20; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 1; r < 20; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r][c + 1] && board[r][c + 1] == board[r][c + 2] && board[r][c + 2] == board[r][c + 3] && board[r][c + 3] == board[r][c + 4] && board[r][c-1]!=board[r][c] && board[r][c+4] != board[r][c+5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 1; r < 16; r++) {
		for (int c = 1; c < 20; c++) {
			if (board[r][c] && board[r][c] == board[r + 1][c] && board[r + 1][c] == board[r + 2][c] && board[r + 2][c] == board[r + 3][c] && board[r + 3][c] == board[r + 4][c] && board[r - 1][c] != board[r][c] && board[r + 4][c] != board[r + 5][c]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 1; r < 16; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r + 1][c + 1] && board[r + 1][c + 1] == board[r + 2][c + 2] && board[r + 2][c + 2] == board[r + 3][c + 3] && board[r + 3][c + 3] == board[r + 4][c + 4] && board[r - 1][c - 1] != board[r][c] && board[r + 4][c + 4] != board[r + 5][c + 5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 5; r < 20; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r - 1][c + 1] && board[r - 1][c + 1] == board[r - 2][c + 2] && board[r - 2][c + 2] == board[r - 3][c + 3] && board[r - 3][c + 3] == board[r - 4][c + 4] && board[r + 1][c - 1] != board[r][c] && board[r - 4][c + 4] != board[r - 5][c + 5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	cout << 0;
}

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

이번에 볼 문제는 백준 2616번 문제인 소형기관차이다.
문제는 아래 링크를 확인하자.

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

dp1[x]를 1번 객차부터 x번 객차까지의 범위에서 K개의 연속한 객차를 하나의 소형기관차를 이용해 끌고갈 때 최대로 옮길 수 있는 손님의 수로 정의하자(단, x는 K보다 크다.). 소형기관차가 객차를 끄는 방법은 x번 객차를 끌거나 끌지 않는 두 가지로 구분할 수 있다. 각 경우의 옮길 수 있는 최대 손님의 수는 dp[x-1]과 dp[x-K], 그리고 x-K+1~x번 객차의 손님의 수의 합을 이용하면 계산해낼 수 있음을 관찰하자. 후자의 값은 prefix sum 배열을 미리 전처리해두는 것으로 빠르게 계산할 수 있다.

위와 같은 방식으로 dp2[x] 및 dp3[x] 또한 정의해 그 값들을 구해내자. 이 때 문제의 답은 dp3[N]이 될 것이다.

이 방법의 시간복잡도는 \(O(N)\)이다.

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

#include <iostream>
using namespace std;

int N, K;
int psum[50001];
int dp1[50001];
int dp2[50001];
int dp3[50001];

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> psum[i];
		psum[i] += psum[i - 1];
	}
	cin >> K;

	for (int i = K; i <= N; i++) dp1[i] = max(dp1[i - 1], psum[i] - psum[i - K]);
	for (int i = K * 2; i <= N; i++) dp2[i] = max(dp2[i - 1], dp1[i - K] + psum[i] - psum[i - K]);
	for (int i = K * 3; i <= N; i++) dp3[i] = max(dp3[i - 1], dp2[i - K] + psum[i] - psum[i - K]);

	cout << dp3[N];
}