취미로 코딩하기

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

이번에 볼 문제는 백준 32775번 문제인 가희와 4시간의 벽 1이다.
문제는 아래 링크를 확인하자.

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

주어진 수를 1회 타노스할 때마다 길이가 \(2^{-1}\)배가 됨을 관찰하자. 따라서 길이가 \(2^N\)을 \(T\)번 타노스하면 만들어지는 수의 길이는 \(2^{N-T}\)가 됨을 알 수 있다.

위의 관찰을 통해 잘 생각해보면 주어진 수의 결과는 앞에서부터 \(N-T\)자씩 끊어 읽은 수 중 하나가 됨을 알 수 있다. 이 중 가장 큰 수를 찾아 문제를 해결하자.

이 때, 주어지는 수 자체의 크기가 매우 크므로 그 값을 직접 저장하기는 곤란할 수 있다. 대신 수를 문자열의 형태로 저장하고 문자열의 대소 비교를 이용해 가장 큰 문자열을 찾는 식으로 구현할 수 있다. 자릿수가 같은 두 수의 크기 비교는 문자열의 비교 결과와 같다는 점을 상기하자.

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

#include <iostream>
using namespace std;

int N, T;
string ans;
string s;

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

	cin >> N >> T;
	T = N - T;
	N = (1 << N), T = (1 << T);
	N /= T;
	while (N--) {
		s.clear();
		for (int t = 0; t < T; t++) {
			char c; cin >> c;
			s += c;
		}
		ans = max(ans, s);
	}
	cout << ans;
}