[백준 1475] 방번호

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

다솜이의 방 번호가 주어지면 필요한 세트의 개수의 최솟값을 구해야한다.

그래서 예를들면

1234 번호가 주어지면 1,2,3,4번 카드가 각각 1장 씩 필요하므로 이렇게 표현이 가능하다.

 

 

이것은 1세트로 가능한 번호이다.

다음 예시로는 1233이 주어졌을때를 보면

 

1,2는 각각 1장 필요하고 3은 2장이 필요하다 이것은 2세트가 있어야 이 방번호를 표현할수있다.

이렇게 위 배열을 표현하기 위해서는 방번호가 주어졌을때 방번호의 숫자를 분리하고 그 숫자에 해당하는 인덱스값을 1씩 증가 시키면 저 배열이 표현이 가능하다.

그다음으로 배열에 있는 값중 가장 큰 값이 우리가 구하려는 세트의 최솟값이다.

다음으로 고려해야할것은 6과 9이다.

 

 

예를들어 669가 주어졌을때

 

1. 6은 그대로 6인덱스에 증가

 

 

2. 6이 주어졌지만 9로 바꿀 수 있다

     

     이말은 즉 6과 9인덱스값중 가장 작은 값을 가진 인덱스값을 1증가 시키면 된다.

 

 

3. 이번엔 9가 주어졌는데 6과 9의 인덱스값이 같으므로 그냥 그대로 주어진 9인덱스의 값에다 1증가

 

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

int numArr[10] = { 0,0,0,0,0,0,0,0,0,0};

int main() {
	string input;
	getline(cin, input);
	for (int i = 0; i < input.length(); i++)
	{
		int st = input[i] - '0';
		//6이나 9가 입력됐을때 두개의 인덱스값중에 작은 곳 증가 
		if (st == 6 || st==9) {
			if (numArr[6] < numArr[9])numArr[6]++;
			else if(numArr[6]>numArr[9]) {
				numArr[9]++;
			}
			else {
				numArr[st]++;
			}
		}
		else {
			numArr[st]++;
		}
		
	}
	int max = -1;
	//이 배열에 들어있는 값중 최댓값 찾기
	for (int i = 0; i <= 9; i++)
	{
		if (numArr[i] > max)max = numArr[i];
	}
	cout << max;

	
	
}