티스토리 뷰
반응형
- 백준 알고리즘 : https://www.acmicpc.net/problem
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.
예제 입력
2
예제 출력
1
곰가드의 코드
a = int(input()) + 1min_cnt = [ -1 for i in range(a)]for i in range(1,a):min_cnt[i] = min_cnt[i-1] + 1if i % 2 == 0:min_cnt[i] = min([min_cnt[i], min_cnt[int(i/2)]+1])if i % 3 == 0:min_cnt[i] = min([min_cnt[i], min_cnt[int(i/3)]+1])print(min_cnt[-1])
동적 프로그래밍을 이용 각 수마다 최소값을 구한 뒤 min_cnt 리스트에 저장해 줍니다.
1을 더했을 때, 2 를 곱했을 때, 3 을 곱했을 때 를 매번 비교하면서 최소값을 추가하는 것이 이 코드의 핵심입니다.
참고할 파이썬 코드
반응형
'#Archive' 카테고리의 다른 글
07. 독버섯 데이터 (0) | 2018.01.19 |
---|---|
2018 카카오 신입 공채 1차 블라인드 코딩테스트 문제 07 (0) | 2018.01.18 |
2018 카카오 신입 공채 1차 블라인드 코딩테스트 문제 06 (2) | 2018.01.17 |
2018 카카오 신입 공채 1차 블라인드 코딩테스트 문제 05 (0) | 2018.01.16 |
다이나믹 프로그래밍 - 동적 계획법 (0) | 2018.01.15 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 첨단산업단지
- PPT
- sql
- 카카오
- 산업단지
- 코딩테스트
- 파이썬
- 딥러닝
- ALIAS
- 리트
- dict
- MLP
- 백준
- 의사결정트리
- 블라인드 코딩
- python
- ML
- 신입 공채
- 리눅스
- 일반산업단지
- KNN
- 넘파이
- 지도학습
- 로스쿨
- 머신러닝
- 알고리즘
- 블라인드
- 시흥
- 광명
- Oracle
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함