백준 1436 - 파이썬

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

문제 풀이

이번 문제는 이해하는데 시간이 걸렸다. 2번째 시리즈는 1666, 3번째는 2666 이렇게 666 앞에 있는 숫자가 하나씩 증가한다는 것은 이해했으나 입력이 500일때 왜 166699가 나오는지 이해를 못했다. 잘 생각해 보니 666이 포함된 숫자의 500번째가 166699라는 것을 알 수 있었고, 구현이 어려워 보이지 않아 바로 코드를 작성해 봤다.

 

n = int(input())
cnt = 0
res = 666

while True:
    if '666' in str(res): # 666이 포함된 수라면 cnt 증가
        cnt += 1
    if cnt == n:
        break
    res += 1

print(res)

 

파이썬은 in 키워드를 이용하면 배열이든 문자열이든 원하는 것이 존재하는지 알아내기 쉽기 때문에 간단히 작성할 수 있었다.

 

다른 풀이는 없을까 싶어 구글링을 해 봤는데 파이썬은 대부분의 사람들이 파이썬 문법을 활용하여 푼 모습이었고, c++를 사용한 사람들 중에서는 다른 방식으로 푼 사람이 있었다.

 

n = int(input())
result = 665
cnt = 0

tmp = 0
while n != cnt:
    result += 1
    tmp = result

    while tmp != 0:
        if tmp % 1000 == 666:
            cnt += 1
            break
        else:
            tmp //= 10

print(result)

 

현재 숫자에 666이 포함되어 있는지 확인하기 위해 일의 자리를 계속 없애면서 확인한 모습이다.

예를 들어 13566698 이라는 숫자가 있을 때, 10으로 나누면 몫은 1356669이고, 나머지는 8이 된다. 여기서 나머지가 일의 자리이므로 버려주면 된다. 이를 반복하면 135666이 되고, 이를 1000으로 나눈 나머지는 666이 되므로 해당 수 안에 666이 들어 있음을 알게 되는 것이다.

 

느낀점

이번 문제는 예제가 이해를 돕기에 부족한 느낌이었다. 7번째 8번째 입력 예제를 보여줬으면 이해가 더 빨라겠지만 그러지 않았기 때문이다. 하지만 이런 문제도 잘 보고 이해하고 푸는 것이 알고리즘의 묘미 아닌가 싶다. 또한 브루트포스 문제들을 풀면서 느낀 점은 인간은 한번에 알아낼 수 있는 규칙이나 공식들을 컴퓨터는 모든 경우의 수를 다 탐색해 봐야 알 수 있는 문제들이 많다는 것을 알게 되었다. 물론 규칙이나 공식을 코드에 잘 녹여내어 풀 수 있는 문제들도 있지만 말이다. 아직은 인간의 방식으로 알고리즘 문제를 풀어내려는 관성이 남아있는데 컴퓨터의 방식으로 풀어내야 할 때는 이를 적절히 잘 활용하는 능력을 알고리즘 문제들을 풀면서 길러나가야 되겠다는 생각이 든다.