일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 데이터베이스
- 그리디 알고리즘
- 브루트포스
- 백준알고리즘
- javascript
- 깊이우선탐색
- 자바스크립트
- SW Expert Academy
- 다이나믹 프로그래밍
- 너비 우선 탐색
- 그래프 이론
- SWEA
- DFS
- 프로그래머스
- 다익스트라
- 브루트포스 알고리즘
- 구현
- 완전탐색
- DP
- Python
- 파이썬
- 스택
- 오라클
- BFS
- 백준 알고리즘
- 문자열
- 너비우선탐색
- 백트래킹
- oracle
- 그래프 탐색
- Today
- Total
민규의 흔적
[Python 파이썬] 백준 1436번 - 영화감독 숌 본문
666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.
입력
첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
알고리즘 분류
- 브루트포스 알고리즘
문제 접근
6이 3개 이상 연속된 수 666이 들어간 모든 종말의 수를 오름차순으로 정렬했을 때, N 번째 종말의 수를 알아내는 문제이다.
666이 들어간 숫자의 대소관계는 규칙을 찾기가 불가능에 가깝기에, 가장 작은 종말의 수인 666부터 1씩 계속 더해보며 해당 수가 종말의 수인지 확인하며 N 번째 종말의 수를 알아내야 한다.
이 방식이 가능한 이유는 N이 최대 10000이며, 시간 제한이 2초이기 때문이다.
실제 정답 코드에서 입력값 N에 10000을 대입했을 때 2666799가 출력되기 때문에 수행시간이 엄청 길지도 않다.
입력 예제
2
3
출력 예제
1666
2666
전체 코드
# 1436
N = int(input())
cnt = 0
num = 666
while True:
str_num = str(num)
if "666" in str_num:
cnt += 1
if N == cnt:
break
num += 1
print(num)
풀이 후기
규칙을 어떻게든 찾아보려다, 찾는 것이 불가능에 가까워 보여 가장 작은 종말의 수 666부터 1씩 더해보며 종말의 수가 맞는지 체크하는 방식을 채택하였다.
정말 무식한 방법이지만 이 문제가 요하는 브루트포스 방식의 풀이방법이 맞지 않을까 싶다.
'BOJ' 카테고리의 다른 글
[Python 파이썬] 백준 2231번 - 분해합 (0) | 2024.06.26 |
---|---|
[Python 파이썬] 백준 2798번 - 블랙잭 (0) | 2024.06.26 |
[Python 파이썬] 백준 2667번 - 단지번호붙이기 (1) | 2024.06.13 |
[Python 파이썬] 백준 2638번 - 치즈 (1) | 2024.06.09 |
[Python 파이썬] 백준 1504번 - 특정한 최단 경로 (0) | 2024.06.07 |