[백준] No.29715 비밀번호 찾기 01

 

29715번: 비밀번호 찾기

경우의 수를 찾는 문제다. 표현이 "집에 들어가는데 걸리는 최대 시간"이라고 적혀있어서 조금 낯설다.

보통이라면 '집에 들어가는데 걸리는 최소 시간'일텐데 말이다.

어찌됐든, 조건에 따라서 걸리는 경우의 수를 먼저 구하고, 시간을 계산하면 된다.

조건은 다음과 같다.

 

1에서부터 9까지의 모든 숫자는 단 한 번씩만 사용할 수 있다. 고로 자릿수는 최대 9자리다.

이 중 몇 자리는 정확하게 기억하고, 몇 군데는 숫자만 기억한다.

경우에 따른 자릿수를 세주면 되는 문제다.

 

예제 입력 1을 이용해서 어떤 구조로 돌아가나 확인해보았다.

4자리일 때, 1번째 자리를 2로, 4번째 자리를 8로 채웠다.

그리고 1과 3으로 나머지 2자리를 채워야 한다.

만들 수 있는 경우의 수는 (1, 3)과 (3, 1)로 2가지가 된다. 그리고 최대 시간은 6초다.

여기서, (1, 3)을 이용해서 2138이라는 비밀번호를 '입력'하는데 걸리는 시간이 X(3)초라는 걸 알 수 있다.

해석하자면, '(가능한 경우의 수) x 3'초가 비밀번호를 입력하는데 총 걸린 시간이다.

 

예제 입력 2도 알아보자.

아무 것도 힌트로 주어지지 않은 경우이다. 그때는 1부터 9까지 한 번만 사용하여 자릿수를 채우는 상황이다.

즉 자릿수만큼 경우의 수를 곱해주면 된다. 4자리니까 9 * 8 * 7 * 6으로 9P4와 동일하다.

가능한 경우의 수는 모두 3024로 {(가능한 경우의 수) * 3} + {(가능한 경우의 수) / 3 * 10} 식대로 계산하면 된다.

최종적으로 19152초가 걸리는데, 정답인 19142초와는 다르다.

그 이유는 3024번의 마지막 시도는 '정답'이기 때문에 틀려서 초기화에 드는 시간을 기다리지 않는다.

즉 경우의 수가 3의 배수가 된다면, 1을 빼줘야 한다.

대충 느낌을 알았으니 코드를 작성해보자.

 

# ---------- Import ----------
from itertools import permutations
import sys
input = sys.stdin.readline


# ---------- Function ----------
def cal_time(p, it, wt):
    if p % 3:    
        return (p * it) + (p // it * wt)
    else:
        return (p * it) + ((p-1) // it * wt)

가장 처음에 조건을 파악하고 생각나는대로 적은 코드를 따라가보자.

우선 라이브러리 호출과 함수 부분부터 살펴보자.

가능한 경우의 수를 사용하기 위해 '조합론'의 개념을 사용했다.

이때 permutation(순열)을 써야하나 combination(조합)을 써야하나 고민했지만, 답은 순열이다.

예제 입력 1에서 봤든 (1, 3)과 (3, 1)은 다른 방법이다. 즉 순서를 고려해야 한다.

'조합론'은 경우의 수를 따지는 수학 분야로, 모든 경우의 수 방법이 여기에 속한다.

조합(combination)만이 조합론의 하위 개념이 아님을 명심하자.

 

그리고 시간을 계산하는 함수를 따로 만들어줬다.

Main 부분에서 코드를 적다가 시간을 계산하는 긴 코드가 나와버리면 복잡할 것 같았다.

p, it, wt는 각각 possible(가능한 경우의 수), input_time(입력에 걸리는 시간), wrong_time(초기화에 걸리는 시간)이다.

예제 입력 2에서 본 것처럼 3의 배수일 때와 아닐 때로 구분하여 계산해야 한다.

3의 배수일 때 먼저 1을 빼고 나누나, 나눈 다음에 1을 빼나 값이 같기 때문에 상관없다.

나누기(/) 연산이 아니라, 몫 연산(//)을 해줬기 때문이다.

 

# ---------- Main ----------
pw_length, remember = map(int, input().split())
pw_input_time, wrong_time = map(int, input().split())

if not remember:
    init = 9
    answer = 1
    for _ in range(pw_length):
        answer *= init
        init -= 1
        
    print(cal_time(answer, pw_input_time, wrong_time))
    
else:
    PASSWORD = [0] * pw_length
    possible = []

    for _ in range(remember):
        isZero, num = map(int, input().split())
        
        if isZero: PASSWORD[isZero-1] = num
        else: possible.append(num)

    possible = len(list(permutations(possible, len(possible))))
    print(cal_time(possible, pw_input_time, wrong_time))

4가지 값을 입력받고 크게 두 가지 경우로 나누었다.

힌트가 하나도 없는 경우(not remember), 힌트가 하나라도 있는 경우(else).

힌트가 하나도 없는 경우는 예제 입력 2와 같다.

9P(자릿수)를 해주면 된다. 이때 permutations 라이브러리는 굳이 사용할 필요가 없어보였다.

permutations 라이브러리를 사용하면, 개수가 아니라 가능한 모든 조합을 직접 구한다.

4자리라면, 1234, 1235, 1236, 1237, 1238, 1239, ..., 9875, 9876 이런 식으로 말이다.

하지만 4자리라면 그냥 9 * 8 * 7 * 6만 하는 게 훨씬 빠르지 않나?라고 생각했다.

그래서 for문으로 O(N), N이 최대 9인 시간복잡도가 되었다.

 

아닌 경우는 실제로 PASSWORD를 적어보았다.

possible은 가능한 숫자들을 조합하기 위해서 선언해두었다.

숫자 두 개를 받고, 앞의 숫자(isZero)가 값이 있다면 0이 아니니, 정확하게 PASSWORD를 채워준다.

만약 0이라면, 경우의 수 조합에 사용해야 하니, possible에 추가해준다.

그리고나서 possible의 길이만큼 순열을 세주고 계산한다.

(지금보면 엉망진창인 코드지만, 당시에는 잘 몰랐다.)

 

틀렸다. 왜 틀렸지?라는 생각을 해보았다.

예제에서는 길이만큼 힌트가 주어졌을 때와 힌트가 아예 없는 경우밖에 없다.

힌트가 하나만 있다거나? 두 개처럼 일부만 주어지는 경우에 틀린 게 아닐까? 생각했다.

 

TestCase 1(왼쪽), TestCase 2(가운데), TestCase 3(오른쪽)

? 뭔가 이상하다. 경우의 수를 바꿨는데 왜 다 정답이 3이지?

TestCase 1 상황은, 불확실한 거 하나만 있는 상황이다.

possible에 1개가 있기는 하지만, 나머지 비어있는 칸을 채우는 코드를 작성하지 않았다.

그래서 1 하나에 대해서만 비밀번호를 입력했고, 3초가 걸린 것이다.

TestCase 2 상황은, 확실한 거 하나만 있는 상황이다.

possible에 하나도 없는 상황이다. 하지만 permutations에서는 ()으로 들어가서 1개가 있다고 인식해버린다.

원래는 없어야 하지만, TestCase 1처럼 3초가 걸린다.

TestCase 3 상황은, 확실한 거 하나, 불확실한 거 하나가 있는 상황이다.

TestCase 3도 위의 2개와 마찬가지로 나머지 숫자에 대한 코드가 없었다.,

 

정리해보자면, 4자리에서 4개 힌트와 아예 힌트가 없는 경우에 대해서만 코드를 짠 것이다.

모든 경우의 수에 대비해서 코드를 짜야 한다. 수학적으로 생각을 한번 해보자.

 

예를 들어서 4자리 숫자가 PASSWORD고, 힌트로 1만을 알고 있는 상황이라고 해보자.

그럼 1의 자리를 고정하고 나머지 숫자들이 올 수 있는 경우의 수를 센 것과 동일하다.

1이 올 수 있는 경우의 수를 먼저 세야 한다.

현재 자리가 전부 비어있기 때문에, 전체 자리에서 1이 들어갈 자리를 찾으면 된다. 따라서 4P1이다.

그리고 남은 자리를, 남은 숫자들로 채우면 된다.

현재 위의 상황을 기준으로 남은 자리는 3자리, 남은 숫자는 8개다.

즉, 숫자들에서 3개를 순열로 뽑는 경우와 똑같다. 8P3이다.

그럼 가능한 모든 경우의 수는 4P1과 8P3의 곱이다.

 

가령 위치는 모르고 숫자만 아는 경우로 1과 3이 주어졌다면 어떨까?

전체 4자리 중에서 아는 숫자 2개가 들어올 경우의 수, 4P2.

남은 2자리 중에서 남은 숫자 7개가 들어올 경우의 수, 7P2.

따라서 모든 경우의 수는 4P2 * 7P2다.

 

위치와 숫자를 모두 아는 확실한 경우가 들어온다면?

그 부분은 아예 고려할 필요가 없어진다. 숫자와 전체 길이를 빼면 된다.

이런 수식을 기반으로 코드를 다시 짜보자.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline


# ---------- Function ----------
def nPm(n, m):
    answer = 1
    for _ in range(m):
        answer *= n
        n -= 1
        
    return answer


def cal_time(p, it, wt):
    if p % 3:
        return (p * it) + (p // 3 * wt)
    else:
        return (p * it) + ((p // 3 - 1) * wt)

Import와 Function에 대한 코드다.

우선 permutation 라이브러리를 뺴고, nPm 함수를 만들어주었다.

필요한 건 경우의 수지, permutation으로 모든 경우의 수를 직접 하나하나 구하려는 게 아니다.

nPm은 간단하게 n부터 1씩 줄여가면서 m개의 수를 곱하는 함수다.

 

cal_time에서 잘못 작성한 부분이 있어서 수정해주었다.

처음에 p // it * wt로 작성해주었는데, p // 3 * wt가 맞는 코드다.

왜냐하면 틀려서 초기화를 기다리는 경우는, 무조건 연속 3번 틀린 경우이기 때문이다.

input_time번만큼 틀린 경우가 아니라는 이야기다.

헷갈린 이유는 모든 예제가 input_time의 값이 3이라서 헷갈렸다...!

이 부분을 놓쳐서, WA가 엄청나게 떴었다. 변수를 헷갈리지 않게 유의하자.

 

# ---------- Main ----------
pw_length, remember = map(int, input().split())
pw_input_time, wrong_time = map(int, input().split())
cards = [i for i in range(1, 10)]

if not remember:
    possible = nPm(len(cards), pw_length)
    print(cal_time(possible, pw_input_time, wrong_time))

접근 방식을 다르게 해보았다. 실제 사용할 수 있는 숫자를 cards로 선언해서 뽑아보았다.

만약에 기억하는 숫자(remember)가 하나도 없다면, 바로 nPm을 계산하면 된다.

n은 놓을 수 있는 카드 종류로 9개다. len(cards)가 아니라 9를 넣어줘도 무방하다.

m은 입력받은 패스워드의 길이(pw_length)이다.

시간을 구하기 위한 cal_time() 함수를 호출하면 이 부분 코드는 완성이다.

 

# ---------- Main ----------
else:
    need_num = []
    
    for _ in range(remember):
        isNotZero, num = map(int, input().split())
        
        if isNotZero:
            cards.remove(num)
            pw_length -= 1
            
        else:
            cards.remove(num)
            need_num.append(num)

기억하는 숫자가 하나라도 있는 경우(else)다.

isZero라는 변수명을 isNotZero로 바꿔주었다.

isZero가 True라면, 값이 있다는 이야기인데 isZero와 맞지 않아 한 번 더 생각해주어야 한다.

직관적으로 느끼기 위해 isNotZero로 바꿔, '0이 아닐 때 참이라면'이라고 작성했다.

 

need_num은 숫자는 알지만, 위치를 모르는 숫자 카드를 저장하는 list이다.

isNotZero가 참이라면, 숫자와 위치를 정확하게 아는 것이다.

해당 숫자 카드를 cards 더미에서 뺴주고(cards.remove(num)), 길이를 1개 줄인다.

isNotZero가 거짓이라면, 숫자만 알고 있는 것이다.

따라서 need_num에 추가하고, cards 더미에서는 빼줘야 한다.

 

if not need_num:
    possible = nPm(len(cards), pw_length)
    print(cal_time(possible, pw_input_time, wrong_time))

else:
    condition_1 = nPm(pw_length, len(need_num))
    condition_2 = nPm(len(cards), pw_length-len(need_num))
    possible = condition_1 * condition_2

    print(cal_time(possible, pw_input_time, wrong_time))

need_num이 있는지 없는지 여부에 따라서 경우의 수(possible)를 센다.

만약 위치를 모르는 숫자가 하나도 없는 경우(if not need_num)는 남은 cards로 채우면 된다.

따라서 가능한 경우의 수는 (남은 숫자 카드 개수) P (남은 패스워드 길이)가 된다.

 

need_num이 있다면, 가장 처음 그림을 그려서 구한 경우의 수와 동일하다.

첫 번째(condition_1)로 (가능한 전체 패스워드 길이) P (숫자만 아는 카드 개수)를 구한다.

두 번째(condition_2)로 (남은 숫자 카드 개수) P (남은 패스워드 자리 길이)를 구한다.

모든 경우의 수(possible)은 첫 번째와 두 번째 조건의 곱이다.

 

 

처음에는 간단하다고 생각했는데, 생각보다는 생각을 필요로 하는 문제였다.

간단하다고 생각해서 우선 짜고, 자잘한 수정을 거쳤는데 점점 스파게티 코드가 되었다.

역시 의사 코드를 작성하고 구조를 짜는 게 중요하다는 생각이 들었다.

더욱이 수학적 지식을 잘 공부하고 활용해야 한다고 생각이 들었다.

 

P.S.1

대회 문제를 풀어보려고 하다가 '브실컵'이라는 대회를 발견했다.

그 중 적당한 난이도의 문제를 풀어보려고 '비밀번호 찾기'라는 문제를 선택했다.

그런데 웬 걸 문제 해결에 1시간이나 걸려버렸다...

풀고 보니 잔실수가 너무 많았고, 확실히 의사 코드를 작성하고 들어가는 게 효율적이라는 생각이 들었다.

문제를 풀 때 세세하게 읽고, 조건에 맞춰 한글로 의사 코드를 적어야 한다.

이걸 습관을 들여놔야지 이상한 곳에서 헤매지 않는다.