[C++] 1475번 : 방 번호

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

1475번: 방 번호

풀이

 

한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다.

-> 대놓고 배열을 사용하여 풀라고 한다.

 

문제에서 신경써줘야 하는 부분은

'6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용' 이다.

 

일단 단순하게 방번호가 9999인 경우 2set가 필요함을 알 수 있다.

그렇다면 99999의 경우는?

당연히 3set일 것이다.

이에 따라 홀수/짝수 경우를 나눠

홀수 -> 2로 나누고 + 1 , 짝수 -> 2로 나누기 연산을 수행해서 최댓값을 구하고자 하였으나, 66699 라는 반례가 존재했다.

정답은 3set인데, 위 논리대로라면 v[6] == 3이고 v[9] == 2이니 3 / 2 + 1로 2set가 출력될 것이다.

이는 원하는 결과가 아니다!

 

따라서 toggle을 이용해보기로 하였다.

홀수번째의 6또는 9를 식별 시 요소의 값을 1늘려주고, 짝수번째는 늘려주지 않는 방식이다. (배열의 6이나 9 index만을 취급해야 한다는 점에 주의!)

뮨제는 풀렸지만 코드가 길다.

 

코드

 

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

bool toggle = 1;

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

	vector<int> v(10);

	while (N != 0) {
		int temp = N % 10;
		N /= 10;
		if ((temp == 6 || temp == 9) && toggle == 1) {
			v[6]++;
			toggle = 0;
		}
		else if(temp == 6 || temp == 9){
			toggle = 1;
		}
		else {
			v[temp]++;
		}
	}
	auto max = max_element(v.begin(), v.end());
	cout << *max;
}

 

 

처음 내가 접근했던 홀수/짝수로 접근하는 것이 아닌

같다고 취급하는 것에서 두 수를 더해 2로 나눈다는 마인드가 필요했다. (마치 평균 구하듯이)

이 때 또 주의할 점은 더하고 + 1을 해줌으로써 두 요소의 값 중 큰 값이 최종적으로 출력되게 할 수 있었다.

(혹은! 내 위 코드처럼 배열의 6이나 9 index에 1씩 늘려가고 마지막에 arr[6] + 1 / 2 해도 되었다!)

 

+while(N != 0)은 당연히 while(N)으로 바꿔 사용할 수 있다. 코드를 줄이자!

 

모범 코드

// Authored by : OceanShape
// Co-authored by : BaaaaaaaaaaarkingDog, kiiimiiin
// http://boj.kr/a7a4aa95c4ee446990f868f926993161
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int N, a[10] = {}, ans = 0;
  cin >> N;
  
  // 자리수 추출
  while(N){
    a[N%10]++;
    N /= 10;
  }

  for(int i = 0; i < 10; i++){
    if(i == 6 || i == 9) continue;
    ans = max(ans, a[i]);
  }
  // (a[6]+a[9])/2를 올림한 값이 6, 9에 대한 필요한 세트의 수이므로 (a[6]+a[9]+1)/2을 계산
  ans = max(ans, (a[6]+a[9]+1)/2);
  cout << ans;
}