취미로 코딩하기

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

이번에 볼 문제는 백준 1206번 문제인 사람의 수이다.
문제는 아래 링크를 확인하자.

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

어떤 평균점수가 주어져도 10000명의 사람이 있다면 모든 평균 점수가 나오게끔 사람들이 투표할 수 있음을 관찰하자. 따라서, 1부터 10000까지 사람의 수로 가능한 수치를 하나하나 확인해나가는 완전탐색 풀이로 문제를 충분히 해결할 수 있다.

이 문제의 경우 버림을 통해 소수의 값을 계산함에 유의하자. Long Division(장제법; 초등학생들이 나눗셈의 몫과 나머지 구하던 그 방법)을 직접 구현하면 문제가 요구하는 값을 오차 없이 계산할 수 있다.

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

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

int N;
int A[50];
string s;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		if (s.length() == 6) continue;
		A[i] = (s.front() - '0') * 1000 + stoi(s.substr(2, 3));
	}
	for (int k = 1; k < 10001; k++) {
		bool chk = 1;
		for (int i = 0; i < N; i++) {
			int L = 0, R = k * 10;
			while (L <= R) {
				int mid = (L + R) / 2;
				int val = 0;
				for (int _ = 0; _ < 4; _++) {
					val = val * 10 + mid / k;
					mid %= k;
					mid *= 10;
				}
				if (val < A[i]) L = (L + R) / 2 + 1;
				else if (val > A[i]) R = (L + R) / 2 - 1;
				else goto BREAK1;
			}
			chk = 0;
			goto BREAK2;
			BREAK1:
			1;
		}
		BREAK2:
		if (chk) {
			cout << k;
			return 0;
		}
	}
}