BOJ5671 호텔 방 번호

Hoeun Lee·2021년 8월 18일
0
post-thumbnail

문제

BOJ5671 호텔 방 번호
실버V | 백준 5671 | Python3 파이썬 풀이


알고리즘

조건에 부합한지 체크하는 check(num : int) -> bool 함수를 사용했다.

def check(num : int) -> bool:
    numcheck = {'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0}

    for i in str(num):
        if numcheck[i] == 1:
            return False
        numcheck[i] += 1

    return True
  1. 0부터 9까지 한 자리수 자연수의 출현 빈도를 기록하는 딕셔너리를 선언
  2. 숫자를 한 자리씩 보며 출현 빈도를 카운트
  3. 만약 어떤 숫자가 1번 초과해서 나왔다면 바로 False 반환
  4. 아니라면 True 반환
  • 이 문제의 최대 입력은 5000까지 이므로 1부터 5000까지 DP를 이용해 구간합을 구해놓는다.
    ex) DP[4000]은 1부터 4000까지 가능한 방 번호의 개수
  1. 위 함수를 이용해 구간 합을 구한다.
for i in range(1, 5001):
    DP[i] = DP[i - 1] + (1 if check(i) else 0)
  1. N, M을 입력 받아 구간 합인 DP[M] - DP[N - 1]을 출력한다.
  • 이 문제는 특이하게 입력의 끝을 EOF 시그널로 판단하므로 try-except문을 이용한다. (백준 문제를 풀다보면 가끔 입력이 이와 같은 문제를 만날 수 있으니 알아두자)

코드

import sys

input = sys.stdin.readline

def check(num : int) -> bool:
    numcheck = {'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0}

    for i in str(num):
        if numcheck[i] == 1:
            return False
        numcheck[i] += 1

    return True


DP = [0] * 5001

for i in range(1, 5001):
    DP[i] = DP[i - 1] + (1 if check(i) else 0)

while True:
    try:
        N, M = map(int, input().split())
        print(DP[M] - DP[N - 1])
    except:
        break

결과


최댓값 5000을 잘못 봐서 틀렸다.

profile
건국대학교 컴퓨터공학부 이호은 | 알고리즘 정리 블로그

0개의 댓글