처음에 이 문제를 봤을 때에는 단순하게
'뭐야~ 앞에 숫자 붙이면 되는 거 아냐~ㅎ'
라고 생각했다가 장렬히 틀리고 문제를 다시 읽어 보았다.
여기서 기가 막힌 조건이
숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.
다시 한 번
N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.
1부터 10,000까지의 숫자 안에서 작은 수부터 큰 수가 될 때까지
'666'이 연속으로 들어가는 숫자에 번호를 매긴 뒤
그 번호는 n번째 영화 제목에 붙는 것이다.
그래서 문제 풀이의 개요는 1부터 10,000까지의 숫자 중에서
'666'이 들어간 숫자를 찾고 그 숫자가 몇 번째 숫자인지
반환해주면 되는 것이다.
n = int(input())
nth = 666
count = 0
while True:
if '666' in str(nth): #1 n번째 수에 '666'이 포함되어 있다면(str이 아니면 무조건 1의자리부터 시작하니까)
count+=1 #2 카운트를 올려라
if count == n: #4 카운트랑 n번째 수가 같다면
print(nth) #5 nth를 출력하고
break #6 while문을 종료해라
nth+=1 #3 666이 포함된 수가 나올 때 까지 nth를 1씩 증가 시킨다
이 문제에서 관건은 '666'과 카운트를 문자열로 바꾸고 자리에 상관없이
포함되어 있으면 번호를 매기는 것이다.
이 문제에서 쓰이는 개념은 브루트 포스 라는 개념이다.
'브루트 포스'는
암호학에서, 무차별 대입 공격(영어: brute-force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다.
암호학에서 시작하여 알고리즘에서는 1부터 모든 수를 대입해보는 것을 의미한다.
그래서 문제를 보면 1씩 추가하면서 '666'이 들어가는 수를 찾는 걸 알 수 있다.
요구 조건에 충족하는 결과만을 출력하기 때문에 정확도는 높지만
1부터 하나하나 대입하는 만큼 (길이가 길 수록) 시간과 비용이 높다는 것이
단점이 된다.
문제 해결에 있어서 브루트 포스 개념은
문제를 선형 구조로 구조화 한 후,
적당한 해를 찾을 때까지 탐색,
찾은 후에 정리하는 방식으로 쓰이고
프로그래밍(더불어 코딩 테스트) 에서 자주 쓰이는 DFS,BFS 중
BFS에서 많이 쓰이는 개념이라고 하는데 이는 좀 더 정리가 되어야
설명할 수 있을 것 같다.
