[BOJ:1475] 방 번호

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

Note

첫 번째 풀이

선형적으로 입력된 숫자 하나하나에 대해 사용된 플라스틱 숫자 개수를 카운트 해준다. 사용된 숫자 개수는 플라스틱 숫자를 꺼낸 박스의 번호를 의미한다. 박스는 1번부터 순서대로 사용한다. 단, 6, 9의 경우, 6일때는 9를 대신 사용할 수 있는지 9일 때는 6을 대신 사용할 수 있는지 체크해서 사용할 수 있다면 대체 숫자를 카운트해준다.

플라스틱 숫자 사용 개수가 가장 마지막의 사용한 박스번호라는 점을 이용하면 대체 숫자 사용여부를 체크할 수 있는데 현재 체크할 숫자가 6이라면 6번 숫자를 쓰기위해 최근에 사용한 박스번호와 9번숫자를 쓰기위해 최근에 사용한 박스번호를 비교해서 9를 위한 박스번호가 더 작다면 9를 대신 사용한다. 예를 들면 현재 6과 9의 최근 사용 박스번호가 각각 2,1이라면 6은 2번 사용했고, 최근 사용한 박스번호는 2이라는 의미이다. 9는 1번 사용했고, 최근 사용한 박스번호는 1이라는 의미이다. 이때 1번 박스의 아직 사용하지 않은 9를 이용해 6을 대체재로 사용할 수 있으므로 3번 박스의 6을 새로 꺼내기 보다는 1번박스의 9를 사용하는 것이 최소의 세트를 사용하는 것이다. 반대의 경우도 마찬가지다.

이를 코드로 표현하면 다음과 같다.

if number = 6:
    if box_number[6] > box_number[9]:
        box_number[9] += 1
    elif box_number[6] <= box_number[9]:
        box_number[6] += 1

두 번째 풀이

첫 번째 풀이말고 다른 풀이법도 존재했다. 일단 주어진 숫자가 6 이든지 9 든지 상관없이 다른 숫자와 마찬가지로 모두 몇개의 플라스틱 숫자가 필요한지 계산한다. 이렇게 구한 값들로 최소 세트수를 구할 수 있다. 예를 들면 숫자 9 사용개수가 10개고, 6 사용개수가 0개라면 5개 5개씩 사용하는게 사용 세트수를 줄이는 방법이다. 9와 6을 똑같이 분배하는 것이다. 예를 들면 9가 4개 6이 1개로 필요한 방번호였다면, 숫자 9에서 네개중 하나는 6으로 대체하면 9 세개 , 6 두 개로 사용이 가능하다. 이럴 경우 9의 개수와 6의 개수를 더해서 2로 나누면 똑같이 분배가 가능하다. 단, 주의 사항이 있는데 홀수의 경우 2로 나누면 똑같이 분배되지 않는 하나는 버려지므로 1을 더해줘서 나누어 주어야 한다. 이것은 사실 수의 특성상 짝수의 경우도 1을 더해서 나누어 주면 1은 버려지기 때문에 기존 짝수를 나눈 것과 같은 결과가 나오므로 짝수든 홀수든 1을 더해서 나누어 주면 똑같이 분배가능한 수를 구할 수 있다. 그리고 홀수의 경우 하나가 더 많게 분배되는 것은 어차피 최대 값을 구하는 것이기 때문에 무시가 가능하다.

 

만약 이렇게  정수론 관점으로 이해가 되지 않는다면, 규칙 발견으로도 구할 수 있다.  예를 들어 9와 6이 각각 1번씩 쓰였다면 최소 세트수 1, 9과 6이 각각 2번 1번씩 쓰였다면 세트수 2, 9와 6이 각각 7번 0번씩 쓰였다면 세트수 3으로 구할 수 있다. 9와 6의 개수합 +1을 나눈 몫이 최소 세트수라는 규칙을 구할 수 있다. 다른 경우를 해보아도 규칙은 똑같이 나온다.

 

Code

import sys
input = sys.stdin.readline

input_number = int(input())
cur_box_number = [0 for _ in range(10)]
while input_number != 0:
    number = input_number % 10
    input_number = input_number//10

    if number == 6:
        if cur_box_number[6] <= cur_box_number[9]:
            cur_box_number[6] += 1
        elif cur_box_number[6] > cur_box_number[9]:
            cur_box_number[9] += 1
    elif number == 9:
        if cur_box_number[9] <= cur_box_number[6]:
            cur_box_number[9] += 1
        elif cur_box_number[9] > cur_box_number[6]:
            cur_box_number[6] += 1
    else:
        cur_box_number[number] += 1
print(max(cur_box_number))