nonneng.ee
Daeun-rithm
nonneng.ee
전체 방문자
오늘
어제
  • 분류 전체보기 (51)
    • Back-end (17)
      • Server (3)
      • Database (3)
      • Spring (9)
      • Node.js (1)
    • Book (1)
      • 이펙티브 자바 (0)
      • 대규모 시스템 설계 (1)
    • Algorithm (1)
      • Greedy, Implementation (6)
      • Dynamic Programming (5)
      • Data Structure (3)
      • Sorting (2)
      • Concept (1)
    • TIL (11)
    • Software (3)
      • Design Pattern (3)
    • Computer Science (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • DP
  • 아이템9
  • 소스설치
  • APM
  • 수동설치
  • node js
  • Java
  • Spring
  • 아이템8
  • 서버
  • jwt
  • 가상머신
  • 아이템 25
  • 구현
  • 브루트포스
  • MySQL
  • Restful API
  • 아이템6
  • 우분투
  • 아이템 23
  • 파이썬
  • 에러
  • Postman
  • 자바
  • 백준
  • 구동원리
  • JPA
  • 컴파일설치
  • API
  • 이펙티브 자바

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
nonneng.ee

Daeun-rithm

Algorithm/Greedy, Implementation

[Python] 백준 #18111 마인크래프트

2022. 3. 8. 17:33

18111번: 마인크래프트 (acmicpc.net)

 

18111번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게

www.acmicpc.net

  • 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업
  • 세로N, 가로M 크기의 집터, 맨 왼쪽 위의 좌표 (0, 0)

 

  • 좌표 (i, j)의 가장 위에 있는 블록 → 인벤토리 : 1초
  • 인벤토리 → 좌표 (i, j)의 가장 위에 있는 블록 위에 놓음 : 2초
  • 0 ≤ 땅의 높이 ≤ 256

땅을 고르는 데 걸리는 최소시간의 (시간, 높이) 출력 (높이가 가장 높은 답)

💡 알고리즘

구현, 브루트포스 알고리즘

💡 접근

처음에는 가장 많이 나오는 수를 기준으로 더 높은 블럭/ 낮은 블럭을 센다 → 가장 높은 높이부터 되는지 안되는지 check

이 방법으로 코드를 작성하였으나.. 땅의 높이가 제한적이기 때문에 굳이 가장 많이 나타나는 높이를 기준으로 생각할 필요가 없었다.

→ (0 ~ 256) 모든 높이에 대하여 가능한지 check

💡 코드

import sys

N, M, B = map(int, sys.stdin.readline().split())

arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

height = 0
minn = 1000000000000000000000000000000
for i in range (257) :
    up = 0
    down = 0
    for j in range (N) :
        for k in range (M) :
            if arr[j][k] < i :
                up += i -arr[j][k]   # 블럭을 올리는 경우
            else :
                down += arr[j][k] - i    # 블럭을 치우는 경우
    inven = down + B
    if inven < up :
        continue
    time = down * 2 + up
    if time <= minn :
        minn = time
        height = i
print(minn, height)
  • 불필요한 계산을 줄이기 위한 inven < up if문 작성

'Algorithm > Greedy, Implementation' 카테고리의 다른 글

[Java] 백준 #1780 종이의 개수  (0) 2022.05.13
[Python] 백준 #7568 덩치  (0) 2022.02.26
[Python] 백준 #1874 스택 수열  (2) 2021.06.23
    'Algorithm/Greedy, Implementation' 카테고리의 다른 글
    • [Java] 백준 #1780 종이의 개수
    • [Python] 백준 #7568 덩치
    • [Python] 백준 #1874 스택 수열
    • [Python] 백준 #1181 단어 정렬
    nonneng.ee
    nonneng.ee

    티스토리툴바