반응형
밑의 링크는 백준에서의 문제 링크입니다.
14606번: 피자 (Small)
예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작
www.acmicpc.net
파이썬 코드와 결과입니다.
# readline을 사용하기 위해 import합니다.
from sys import stdin
# 첫 번째 줄에 피자판의 개수인 양의 정수 N을 입력합니다.
# 1 <= N <= 10
# 정수로 변환합니다.
N = int(stdin.readline())
# 즐거움의 총합을 구하면서 생기는 피자탑들을 저장하는 리스트 변수를 선언합니다.
pizza_towers = []
# 즐거움의 총합의 최댓값을 저장할 변수를 선언합니다.
joy = 0
# 처음 피자판의 개수가 1 이상이면
if N > 1:
# 피자탑 리스트 변수에 N을 넣어줍니다.
pizza_towers = [N]
# 피자탑 리스트 변수가 비어질 때까지 반복합니다.
while True:
# 피자탑 리스트 변수가 비어있다면
if pizza_towers == []:
# 즐거움의 총합을 출력합니다.
print(joy)
# 반복문을 탈출합니다.
break
# 피자탑 리스트 변수가 비어있지 않다면
else:
# 피자탑 리스트 변수의 맨 끝에서 피자탑을 하나 빼내어 변수에 저장합니다.
pizza_tower = pizza_towers.pop()
# 빼낸 피자탑의 절반을 한 부분으로 변수에 저장합니다.
pizza_tower_part1 = pizza_tower // 2
# 나머지 절반을 변수에 저장합니다.
pizza_tower_part2 = pizza_tower - pizza_tower_part1
# 두 절반의 곱을 즐거움의 총합에 더해줍니다.
joy += pizza_tower_part1 * pizza_tower_part2
# 빼낸 피자탑에서 구한 처음의 절반의 결과가 1이 아니라면
if pizza_tower_part1 != 1:
# 피자탑 리스트 변수에 그 절반의 값을 넣어줍니다.
pizza_towers.append(pizza_tower_part1)
# 빼낸 피자탑에서 구한 두 번째 절반의 결과가 1이 아니라면
if pizza_tower_part2 != 1:
# 피자탑 리스트 변수에 그 절반의 값을 넣어줍니다.
pizza_towers.append(pizza_tower_part2)
맞았습니다 결과를 보고 나서 다른 사람들의 파이썬 결과를 보니 60ms대의 실행 시간을 낸 사람들도 많았습니다.
그런 사람들의 코드를 보고 어떻게 더 실행 시간을 줄였는지 공부해야겠습니다.
그리고 카테고리를 확인해보니 다이나믹 프로그래밍을 의도한 문제였습니다.
저는 문제 풀 때 막연히 절반씩 잘라서 즐거움의 총합에 더하면 최대가 되겠구나 생각하고
코드를 짰고, 위의 다이나믹 프로그래밍은 생각하지 못했는데
다이나믹 프로그래밍을 공부하고 다이나밍 프로그래밍적으로도 짤 수 있는지도 공부해야겠습니다.
※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.
※ 더 효율적이고 빠른 정답을 환영합니다.
반응형
댓글