게임에 나올만한 제목을 가진 문제를 좋아한다. 일단 흥미가 붙기 때문.
그 중에서도 아주 쉬운 문제인 '엘프의 검'이라는 문제를 풀이해보겠다.

BOJ 4436 - 엘프의 검 링크
(2022.09.22 기준 B2)
(설마 이걸 치팅한다고..?)

문제

n이 주어질 때

n, 2n, 3n, 4n, ..., kn

이라는 수열을 만들 때, 0-9까지의 숫자가 전부 나타나게 하는 가장 작은 k

알고리즘

k를 1씩 증가시키면서 kn의 자리마다의 숫자를 체크해가면서 0-9까지의 숫자가 전부 나타나게 되면 중단해야 한다. 이는 k를 증가시키면서 하나씩 확인해봐야 하므로 브루트포스. 그리고 간단한 사칙연산..?

풀이

이 문제뿐만 아니라 앞으로도 이런 유형의 문제가 많이 나올 것이다.
숫자의 모든 자리수를 체크
너무나도 간단해서 사람마다 사용하는 기법이 전부 조금씩은 다를건데, 내가 사용하는 방법은 2가지이다.

1. 수를 문자열로 처리하여 앞에서부터 차례대로 살펴보기

for m in str[n]:
	if not appear[m]:
    	appear[m] = True
        ct += 1

이런 느낌으로 살펴보는데, 당연히 appear 배열은 그냥 리스트로 구현하면 안된다. 지금 인덱스를 문자열로 주기 때문.
그러므로, map이나 dictionary 같은 형태로 만들어서 체크해주자.

2. 수를 10으로 나누면서 나머지를 차례대로 살펴보기

q = n
while q:
	q, r = divmod(q, 10)
    if not appear[r]:
    	appear[r] = True
        ct += 1

1번보다는 좀 생각해야 하는 구조이다. 하지만 이해하고 보면, 정말 간단하면서 테크닉적인 구조이다.

변수의 type를 변환하는 것은 쌓이고 쌓이다 보면, 생각보다 시간이 많이 소요된다. 그러므로 문제를 잘 살펴보고 선택하여 쓸 것.
이 문제는 두 방법 전부 가능하다.

그리고 문제에서의 수열은 kn까지 늘어나는 방식이다. 그러므로 k가 1씩 증가할 때마다 n과 k를 곱해줘도 되겠지만, n을 한번씩 더해주면서 합을 늘려가는 것이 훨씬 간단하고 빠를 것이다.

코드

• 1번 방법

import sys; input = sys.stdin.readline

while True:
    # EOF 처리
    try:
        n = int(input())
    except:
        break

    # 숫자를 문자열로 처리하여 나타나는지 확인할 것이기 때문에 dictionary 형태로 만들자.
    appear = {'0': False, '1': False, '2': False, '3': False, '4': False, '5': False, '6': False, '7': False, '8': False, '9': False}

    rest = 10 # 나타나지 않은 숫자의 개수
    # n, 2n, 3n, ..., kn 형태이므로 n을 더해주면서 자리마다 숫자를 체크해주자.
    S = k = 0

    # 나타나지 않은 숫자의 개수가 0이 될 때까지
    while rest:
        k += 1
        S += n
        for m in str(S): # 자리마다 체크
            if not appear[m]: # 만약 나타나지 않은 숫자이면 체크
                appear[m] = True
                rest -= 1
                if not rest: # 나타나지 않은 숫자가 없으면 탐색 중단
                    break
    print(k)

• 2번 방법

import sys; input = sys.stdin.readline

while True:
    # EOF 처리
    try:
        n = int(input())
    except:
        break

    # 숫자가 나타났는지 확인할 배열
    appear = [False] * 10

    rest = 10 # 나타나지 않은 숫자의 개수
    # n, 2n, 3n, ..., kn 형태이므로 n을 더해주면서 자리마다 숫자를 체크해주자.
    S = k = 0

    # 나타나지 않은 숫자의 개수가 0이 될 때까지
    while rest:
        k += 1
        S += n
        # 몫과 나머지를 이용할 것이다.
        # 몫에 현재 n의 합을 넣어주고
        # 몫이 0이 될 때까지, 10으로 나누어주면서 나머지를 체크
        # 이는 뒤쪽 자리의 숫자부터 살펴보게 되는 것이다.
        q = S
        while q:
            q, r = divmod(q, 10)
            if not appear[r]: # 만약 나타나지 않은 숫자이면 체크
                appear[r] = True
                rest -= 1
                if not rest: # 나타나지 않은 숫자가 없으면 탐색 중단
                    break
    print(k)

여담

B2 다 푸는 날이 언제쯤 올까..?