[210309][백준/BOJ] 1475번 방 번호

문제

입출력

풀이

한 세트에 0부터 9까지의 숫자가 있다.
6과 9는 서로 뒤집어서 이용할 수 있으므로 한세트만으로 66이나 99같은 번호를 사용할 수 있다.

크기가 10인 배열에 ++를 하면서 가장 큰 값이 방 번호를 꾸미는데 필요한 세트의 갯수가 된다.
숫자가 9인 경우에는 문제를 쉽게 해결하기 위해 arr[6]에 ++를 하였다.

최대값을 구할때 6의 경우에는 아래 예시와 같은 규칙으로 해결하면 된다.
ex)
666 -> 2세트가 필요
6666 -> 2세트가 필요
66666 -> 3세트가 필요

arr[6]의 값을 2로 나누고 여기에 2로 나눈 나머지값을 더하면 된다.

tmp = arr[i] % 2;
arr[i] /= 2;
arr[i] += tmp;

코드

#include <bits/stdc++.h>
using namespace std;

int arr[10];
char str[1000001];

int main()
{	
	int max = -10000001, tmp;

	scanf("%s", &str);

	for (int i = 0; str[i] != '\0'; i++)
	{
		if (str[i] - '0' == 9)
			arr[6]++;
		arr[str[i]-'0']++;
	}

	for (int i = 0; i < 10; i++)
	{
		if (i == 6 || i == 9)
		{
			tmp = arr[i] % 2;
			arr[i] /= 2;
			arr[i] += tmp;
		}
		if (max < arr[i])
			max = arr[i];
	}
	printf("%d", max);
}

느낀점

어떤 반례가 존재할지 꼼꼼하게 생각해야겠다고 느꼈다.
많은 분들이 올려주신 반례를 하나하나 해결해가며 문제를 해결하였다.