[C++] 백준 1475번 방 번호

1. 문제이해

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

1475번: 방 번호

 

다솜이는 자기 방 번호를 플라스틱 숫자로 붙이려고 한다.

플라스틱 숫자는 0 ~9 한 세트로 판매하며, 6, 9는 서로 뒤집어서 사용가능하다.

다솜이의 방 번호가 주어질 때, 필요한 세트의 개수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

다솜이의 방 번호가 주어질 때, 필요한 숫자 세트의 개수를 출력하는 문제이다.

단, 숫자세트에는 0 ~ 9 까지의 숫자가 들어있으며, 6과 9는 서로 뒤집어서 사용가능하다.

6과 9가 서로 호환가능하다는 점에 유의해야한다.

아래 예제를 통해 풀이방법을 자세히 알아보자.

 

 

<예제 입력 1>

다솜이의 방 번호가 9999

다솜이의 방 번호를 살펴보면, 9가 4번 필요하다.

9는 4개 이지만 6을 이용해 9를 만들 수 있으므로, 사실상 2세트면 위와 같은 숫자를 만들 수 있다.

 

 

<예제 입력 2>

다솜이의 방 번호가 122

다솜이의 방 번호를 살펴보면, 1이 1번, 2가 2번 필요하다.

한 세트에 0 ~9 까지의 숫자가 하나씩 들어있으므로,

1, 2 를 1개씩 얻기 위해 한 세트, 2를 한번 더 얻기 위해 한 세트를 구매해야하므로, 총 2세트가 필요하다.

 

 

<예제 입력  n>

다솜이의 방 번호가 1126699

다솜이의 방 번호를 살펴보면 1이 2번, 2가 1번, 6이 2번, 9가 2번 필요하다.

여기서, 6과 9 같은 특수 경우를 제외한 경우들 중 최대 빈도수는 1인 2번이다.

6과 9는 각각 2번, 총 4번 나타났으나,두 숫자가 서로 호환 가능하므로, 2번 필요하다.

즉, 6과 9는 (6의 빈도수 + 9의 빈도수) / 2  + 1 (홀수의 경우 + 1 필요) 만큼 필요하다.

 

6, 9의 빈도수와 6, 9를 제외한 숫자의 최대 빈도수를 비교, 더 큰 값이 최종적으로 필요한 세트 수가 된다.

해당 경우, 6과 9의 빈도수 = (2 + 2) / 2 = 2

6과 9를 제외한 숫자의 최대 빈도수 = 2

로 같으므로, 최종적으로 필요한 세트수는 2세트이다.

 

 

위 예제들을 통해 알 수 있듯, 해당 문제의 풀이방법은 다음과 같이 정리할 수 있으며,

작성한 소스코드는 다음과 같다.

 

 

1. 입력받은 방 번호의 각 숫자의 빈도수 체크

2. 6, 9를 제외한 숫자들 중 최대 빈도수 값 체크

3. 6, 9의 빈도수와 2에서 구한 가장 큰 빈도수를 비교, 더 큰 값을 채택

 

 

 

3. 소스코드

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

int main() {
	int N;                  // 방 번호
	int num[10] = { 0, };   // 0 ~ 9 숫자들의 빈도수
	int remain;             // 빈도수를 구하기 위한 변수
	int set;                // 최종적으로 필요한 세트 수 
	int six_nine;           // 6과 9의 빈도수의 합

	cin >> N;
	// 1. 입력받은 방 번호의 각 숫자의 빈도수 체크
	while (N > 0) {
		remain = N % 10;
		num[remain]++;
		N = N / 10;
	}

	// 2. 6, 9를 제외한 숫자들 중 최대 빈도수 값 체크
	set = 0;
	for (int i = 0; i < 10; i++) {
		if (i == 6 || i == 9) {
			continue;
		}
		if (set <= num[i]) {
			set = num[i];
		}
	}

	// 3. 6, 9는 서로 호환가능하므로 빈도수 더해줌.
	six_nine = num[6] + num[9];

	// 4. 6, 9의 빈도수와 2에서 구한 가장 큰 빈도수 비교
	//    더 큰 값이 필요한 세트의 개수

	// 4 - 1. 6, 9의 빈도수가 홀수인 경우
	if (six_nine % 2 == 1) {
		if (set < six_nine / 2 + 1) {
			set = six_nine / 2 + 1;
		}
	}
	// 4 - 2. 6, 9의 빈도수가 짝수인 경우
	else {
		if (set < six_nine / 2) {
			set = six_nine / 2;
		}
	}

	cout << set;

	return 0;
}

2. 문제풀이에서 도출한 방법을 통해 작성한 코드이다.

먼저 방 번호(N)를 입력받고, while문을 통해 1. 방 번호의 각 숫자들의 빈도수를 체크한다.

 

숫자들의 반도수를 체크 한 뒤, 2. 6, 9를 제외한 숫자들 중 최대 빈도수 값을 체크해 set에 대입한다.

3. 6, 9의 빈도수를 더해준 뒤 (호환가능하므로), 4. 6, 9의 빈도수와 2.에서 구한 최대 빈도수 값을 비교한다.

 

만약, 6, 9의 빈도수의 합, 즉, six_nine 변수가 홀수인 경우, + 1을 해주어 비교해주고,

짝수라면 해주지 않은 채 값을 비교한다.

(예를 들어 1166999 의 경우, 6, 9 제외 최대 빈도수는 1의 2번. 6, 9의 빈도수는 5번이다.

해당 경우에는 1, 6, 9 한 세트, 다시 동일하게 한 세트, 그리고 남은 9 한세트, 총 3세트가 필요하다.

하지만 만약, 6, 9의 빈도수는 5번인데, 2로 나누어주기만 하면, 2가 나오게 되고, 총 필요 세트 수는 2가 된다.

이러한 경우를 방지하기 위해 6, 9의 빈도수가 홀수이면, 2로 나눈뒤 1을 더해준다.)

 

주석 없는 코드는 왼쪽 아래 더보기를 참고 바랍니다.😊

<주석 없는 코드>

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

int main() {
	int N;                  
	int num[10] = { 0, };  
	int remain;           
	int set;      
	int six_nine;      

	cin >> N;
	while (N > 0) {
		remain = N % 10;
		num[remain]++;
		N = N / 10;
	}

	set = 0;
	for (int i = 0; i < 10; i++) {
		if (i == 6 || i == 9) {
			continue;
		}
		if (set <= num[i]) {
			set = num[i];
		}
	}

	six_nine = num[6] + num[9];

	if (six_nine % 2 == 1) {
		if (set < six_nine / 2 + 1) {
			set = six_nine / 2 + 1;
		}
	}
	else {
		if (set < six_nine / 2) {
			set = six_nine / 2;
		}
	}

	cout << set;

	return 0;
}

 

 

---

문제에 대한 지적이나 질문은 언제나 감사하게 받고 있습니다.😊