[백준]1475번 방번호

반응형
반응형

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

 

입력

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 필요한 세트의 개수를 출력한다.

 

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

int arr[10];
int main(){
	
	string num;
	cin >> num;
	for(int i =0 ; i < num.length();i++) {
		arr[num[i] -'0']++;
	}
	
	int temp = 0;
	int max = 0;
	int sn = 0;
	for(int i =0; i < 10; i++) {
		if (i == 6 || i == 9) {
		  sn += arr[i];	
		} else {
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		temp = (sn/2) + (sn%2);
	}
	cout << (max > temp ? max : temp);
}

처음 이 문제의 핵심은 6과9의 문제인줄 알았는데 알고 보니 0이 핵심이었다.

나는 이렇게 풀었다. 

6 이랑 9를 쭉 적었다.

0 1

1 0

...

1 5

5 1       예제를 보면 9999의 답은 2였다. 그래서 자세히 보니 규칙 하나를 찾을 수 있었다.

갯수를 전부 더하고 그 값을 2로 나눈 값의 몫과 나머지를 더해 보았다.

9999를 예로 들자면 6과9의 합은 4가 나온다. 몫은 2 나머지는 0이였다. 이 두개를 더 한 값은 놀랍게도 정답인 2와 같았다. 다른 예로 들면 99999 같은 경우 몫은 2 나머지는 1이다. 합은  3이다. 이것 또한 답은 3이다.

하지만 이렇게 풀었더니 나머지를 어떻게 할지 고민되었다. 

더 간단했다. 최대값만 구하면 답이 나왔다. 이제 답의 갯수가 2종류다. 어떤 답이 답일까?

그냥 갯수가 많은게 정답이다. 만약 갯수가 같다면 뭐 상관없다.

예를 들어 2299999 의 답은 3이다. 왜냐하면

필요한 숫자번호세트는 269 269  69 이기 때문이다. 

이렇게 하고 제출을 했는데 틀렸다고 했다. 당황스러웠다. 내가 간과했던게 있는데 그건 0의 존재 여부였다. 지금까지 0은 생각하지 않은 상태에서 진행했다. 0000 을 입력하면 답은 4이다. 하지만 내가 도출한 값은 0이었다. 어디서 부터 잘못된 걸까? 애초에 0은 추가되지 않았다. 그래서 string을 이용해서 값을 구하기로 했다. 알파벳 구할때는 당연하게 하는것들이 숫자를 할때는 당연하지 않았던 것 같다. 아무튼 string을 이용하면 0도 입력하기가 편했다. 

이런식으로 값을 측정하니 놀랍게도 0000의 답은 4로 나왔다. 이렇게 나는 통과했다.

 

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

int b[10];
int m;
int main(){
	string a;
	cin >> a;
	for(int i=0;a[i];i++) {
		b[a[i]-48]++;	
	}
	b[6]=(b[6]+b[9]+1)/2;
	
	for(int i=0;i<9;i++){
		if(b[i]>m) {
			m=b[i];
		}
	}
	cout << m;
}

전체적으로는 나랑 비슷하게 했는데 이 분은 그냥 9의 값과 6의 값을 더해버리고 1을 더한 값을 2로 나누었다. 1을 더한 이유는 균형을 맞추기 위함이 아닐까 생각든다.

그러면  코드가 조금 더 줄어드는 느낌이다.

 

코드길이가 확실히 줄었다. 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2493번 탑  (0) 2020.04.02
[백준] 1158 요세푸스 (list.ver)  (0) 2020.03.31
[백준] 5397번 키로커 (list .ver)  (0) 2020.03.30
[백준] 13300번 방 배정  (0) 2020.03.27
[백준] 10808 알파벳 개수  (0) 2020.03.25

댓글

Designed by JB FACTORY