-
[Python 3] BOJ - 18111 "마인크래프트"BOJ 2020. 3. 7. 23:00
# 문제 링크 : https://www.acmicpc.net/problem/18111
# 풀이 :
Python, PyPy 모두 추가시간이 주어지지 않으므로 도중에 검사하기보다 모든 원소를 돌고나서 체크를 하는것이 낫다. 문제의 조건에서 연산은 두 가지이다.
1) 현재의 높이가 목표 높이보다 낮다면, 인벤토리에서 블록을 꺼내 현재 높이에 붙인다
- 결과 : 현재 높이 1증가, 인벤토리 1 감소
2) 현재의 높이가 목표 높이보다 높다면, 현재 높이의 가장 위의 블록을 인벤토리로 넣는다
- 결과 : 현재 높이 1감소, 인벤토리 1 증가
개인적으로 문제의 핵심은 인벤토리로 들어가는 블록의 갯수와 초기 인벤토리를 합한 것이 인벤토리에서 나가는 블록의 갯수보다 크거나 같다면 그 목표높이로 땅을 고를 수 있다는 것이다.
추가적으로 코드에서는 3중 for문을 돌지만 실제로는 최대 높이가 257개(0 포함), 행렬의 최대 사이즈는 250,000이므로 256 * 250,000 = 64,250,000 이므로 충분히 1초만에 모든 경우를 계산할 수 있다.
# 코드
import sys n, m, b = map(int, sys.stdin.readline().split()) table = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] height = 0 ans = 1000000000000000000000000000000 for i in range(257): max = 0 min = 0 for j in range(n): for k in range(m): if table[j][k] < i: min += (i - table[j][k]) else: max += (table[j][k] - i) inventory = max + b if inventory < min: continue time = 2 * max + min if time <= ans: # 시간이 같을 때는 높이가 높은 순으로 출력하라는 조건에 맞게 # for i in range(257)은 항상 i가 오름차순으로 돌기 때문에 # 시간이 같아도 최종적으로는 높이가 높은 순으로 나오게 된다 ans = time height = i print(ans, height)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1149 "RGB 거리" (0) 2020.03.11 [Python 3] BOJ - 1018 "체스판 다시 칠하기" (1) 2020.03.10 [Python 3] BOJ - 1654 "랜선 자르기" (1) 2020.03.08 [Python 3] BOJ - 16562 "친구비" (0) 2020.03.08 [Python3] BOJ - 1011 "Fly me to the Alpha Centauri" (0) 2020.03.06