취미로 코딩하기

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

이번에 볼 문제는 백준 2840번 문제인 비밀번호이다.
문제는 아래 링크를 확인하자.

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

문제를 해결하는 데에 필요한 조작은 바퀴의 시계방향 다음 칸의 문자가 무엇인지와 반시계방향 다음 칸의 문자가 무엇인지를 알아내는 것이다. 이는 deque 자료구조를 이용해 간단하게 탐색할 수 있다.

하나의 칸에 여러 문자가 등장할 수 있어 모순이 일어나는 경우 외에도 전체 바퀴에 중복되는 문자가 등장해도 안 됨에 유의해 구현하자.

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

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

int N, K;
deque<char> que;
bool visited[128];

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) que.push_back('?');
	while (K--) {
		int M; char c; cin >> M >> c;
		M--;
		while (M--) {
			que.push_back(que.front());
			que.pop_front();
		}

		if (que.front() == '?') {
			if (visited[c]) {
				cout << '!';
				return 0;
			}
			que.push_back(c);
			que.pop_front();
			visited[c] = 1;
		}
		else if (que.front() == c) {
			que.push_back(c);
			que.pop_front();
		}
		else {
			cout << '!';
			return 0;
		}
	}

	while (!que.empty()) {
		cout << que.back();
		que.pop_back();
	}
}

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

이번에 볼 문제는 백준 2865번 문제인 나는 위대한 슈퍼스타K이다.
문제는 아래 링크를 확인하자.

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

각 참가자마다 받은 가장 높은 점수를 기준으로 점수가 가장 높은 K명을 골라 그 점수의 합을 구하는 문제이다.

주어지는 참가자의 번호는 1-based이므로 0-based 배열에서의 정렬을 이용하고자 할 경우 이에 유의해 구현하자.

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

#include <iostream>
#include <algorithm>
using namespace std;
typedef long double ld;

int N, M, K;
ld arr[100];
ld ans;

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

	cin >> N >> M >> K;
	while (M--) {
		for (int i = 0; i < N; i++) {
			int idx; ld x; cin >> idx >> x;
			idx--;
			arr[idx] = max(arr[idx], x);
		}
	}

	sort(arr, arr + N);
	for (int i = 1; i <= K; i++) ans += arr[N - i];


	cout << fixed;
	cout.precision(1);

	cout << ans;
}

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

이번에 볼 문제는 백준 2823번 문제인 유턴 싫어이다.
문제는 아래 링크를 확인하자.

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

주어진 모든 '.' 칸에 대하여 사방으로 이어진 칸 중 'X'가 셋 이상 있는 칸이 존재하는지를 살펴 문제를 해결하자.

주어지는 지도의 상하좌우로 'X'로 이루어진 행과 열을 하나씩 추가하면 경계 부분에 대한 예외처리를 할 필요가 없어 간편히 문제를 해결할 수 있다.

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

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

int R, C;
string board[12];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

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

	cin >> R >> C;
	for (int c = -1; c < C; c++) board[0] += "X";
	for (int r = 1; r <= R; r++) {
		cin >> board[r];
		board[r] = "X" + board[r] + "X";
	}
	for (int c = -1; c < C; c++) board[R + 1] += "X";

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (board[r][c] == 'X') continue;
			
			int cnt = 0;
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (board[rr][cc] == 'X') cnt++;
			}

			if (cnt > 2) {
				cout << 1;
				return 0;
			}
		}
	}

	cout << 0;
}

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

이번에 볼 문제는 백준 2994번 문제인 내한 공연이다.
문제는 아래 링크를 확인하자.

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

각 멤버의 쉬는 시간을 구성하는 것을 다르게 모델링하면 주어지는 각 공연시간과 길이의 막대기들을 모두 사용해 길이가 각각 T 이하인 두 개의 긴 막대기를 만드는 문제로 생각할 수 있다. 두 문제가 동치임은 어렵지 않게 관찰 가능하므로 설명을 생략한다.

위의 막대기 문제는 T 이하의 길이 중 주어진 막대기들의 일부를 이용해 구성할 수 있는 가장 긴 길이를 찾는 것으로 해결할 수 있다. 답의 존재성이 보장되어있으므로 남은 막대기들의 길이의 합 또한 자연스럽게 T 이하가 될 것이다. 이와 같은 길이는 knapsack dp를 이용해 간단히 구할 수 있다.

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

#include <iostream>
using namespace std;

int T, N;
int resting[501];
int dp[5001];

int idx;
int visited[5001];
int psum1, psum2;

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

	cin >> T >> N;
	for (int i = 1; i <= N; i++) cin >> resting[i];
	
	dp[0] = -1;
	for (int i = 1; i <= N; i++) {
		int r = resting[i];
		for (int t = T; t >= r; t--) {
			if (!dp[t] && dp[t - r]) dp[t] = i;
		}
	}

	idx = T;
	while (!dp[idx]) idx--;
	while (dp[idx] > -1) {
		visited[dp[idx]] = 1;
		idx -= resting[dp[idx]];
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i]) {
			cout << psum1 << ' ';
			psum1 += resting[i];
		}
		else {
			cout << psum2 << ' ';
			psum2 += resting[i];
		}
	}
}

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

이번에 볼 문제는 백준 2993번 문제인 세 부분이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열을 세 부분으로 나누는 경우의 수가 매우 적음을 관찰하자.

따라서 모든 가능한 방법으로 문자열을 나눠 각각을 뒤집고 합해본 다음 그중 가장 사전순으로 빠른 문자열을 출력해 문제를 해결할 수 있다.

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

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

string s; int slen;
string ans = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";

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

	cin >> s;
	slen = s.length();
	for (int i = 1; i < slen; i++) {
		string s1 = s.substr(0, i);
		reverse(s1.begin(), s1.end());

		for (int j = i + 1; j < slen; j++) {
			string s2 = s.substr(i, j - i);
			string s3 = s.substr(j, slen - j);
			reverse(s2.begin(), s2.end());
			reverse(s3.begin(), s3.end());

			string tmp = s1 + s2 + s3;
			if (tmp < ans) ans = tmp;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 2992번 문제인 크면서 작은 수이다.
문제는 아래 링크를 확인하자.

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

문제에서 구하고자 하는 답은 주어진 수의 각 자리의 나열(순열) 중 주어진 나열 다음으로 큰 나열을 찾는 것과 같다.

c++의 경우 주어진 순열의 다음 순열이 존재할 경우 해당 순열로 바꾸고 1을 리턴, 그렇지 않을 경우 첫 순열로 바꾸고 0을 리턴하는 함수인 next_permutation을 이용해 문제를 간단히 해결할 수 있다.

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

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

string s;

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

	cin >> s;

	if (next_permutation(s.begin(), s.end())) cout << s;
	else cout << 0;
}