beeimp
BeeImp
beeimp
전체 방문자
오늘
어제
  • 분류 전체보기 (110)
    • Program_Language (17)
      • Python (13)
      • Go (0)
      • JavaScript (4)
      • TypeScript (0)
      • Rust (0)
      • Solidity (0)
    • OS (8)
      • UNIX&LINUX (7)
      • Windows (0)
      • MacOS (1)
    • Front-End (19)
      • Svelte (19)
      • React (0)
    • Blockchain (6)
      • Bitcoin (0)
      • Ethereum (1)
      • Klaytn (0)
      • Project (5)
    • Data Structure&Algorithm (11)
      • Greedy (7)
      • Dynamic Programming (1)
      • Sort (0)
      • DFS & BFS (2)
      • Recursive (1)
    • Security (0)
      • SDP (0)
      • Authentication (0)
    • Network (3)
      • OpenWrt (0)
      • SDN&NFV (1)
    • Git (5)
    • IT_News (0)
    • 베타 학습단 (12)
      • SQL (12)
    • Project (1)
    • Issues (1)
    • Reviews (3)
    • I Learned (23)
      • TIL (23)
      • WIL (0)
    • Other (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Git
  • mysql
  • PYTHON
  • 탐욕법
  • sql
  • solidity
  • Ethereum
  • javascript
  • Nest.js
  • blockchain
  • jenkins
  • svelte
  • 블록체인
  • react
  • ubuntu
  • Docker
  • github
  • 기초
  • greedy
  • typescript

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
beeimp

BeeImp

Data Structure&Algorithm/Greedy

도서관 - [백준 1461번]

2021. 7. 14. 17:46

도서관 - 백준 1461번

문제

  • 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수 계산하는 프로그램 작성
  • 세준이는 0에 위치, 책도 전부 0에 반납
  • 한 걸음에 1칸씩, 최대 M권을 들 수 있고, 다시 0으로 돌아올 필요 없다.

입력

  • 첫째 줄 - 책 개수 N, 한 번에 들 수 있는 책의 개수 M
  • 둘째 줄 - 책의 원래 위치

출력

  • 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수

코드

import sys


''''
  왼쪽(음수)과 오른쪽(양수)로 나뉨
  책들 모두 들면 다시 돌아와야하기 때문에 *2
  책을 모두 제자리에 두고 그 자리에서 끝나기 때문에 최대값에서는 *1만 하기 때문에
  책의 최대 거리 * 2 - 최대값 으로 계산함
'''
def solution(M, originLocations):
  result = 0

  '''음수 부분과 양수 부분'''
  leftLocations, rightLocations = [], [] 
  for originLocation in originLocations:
    if originLocation < 0:
      leftLocations.append(originLocation)
    else:
      rightLocations.append(originLocation)

  leftLocations.sort() # 왼쪽은 음수기 때문에 오름차순으로 정렬
  for i, leftLocation in enumerate(leftLocations):
    if i % M == 0:
      result -= leftLocation * 2 # 음수기 때문에 빼기

  rightLocations.sort(reverse=True) # 오른쪽은 양수기 때문에 내림차순으로 정렬
  for i, rightLocation in enumerate(rightLocations):
    if i % M == 0:
      result += rightLocation * 2 # 양수기 때문에 더하기

  locations = leftLocations + rightLocations # 계산을 편하게 하기 위해 두 리스트 합치기
  locations.sort() # 오름차순으로 정렬

  if locations[0] < 0: # 두 방향이 존재한다면
    result -= max([abs(locations[0]), locations[-1]]) # 절대값으로 양 끝의 큰 값 중 최대값 빼기
  else:
    result -= locations[-1] # 최대값 빼기


  return result

N, M = map(int, sys.stdin.readline().split())
originLocations = list(map(int, sys.stdin.readline().split()))
print(solution(M, originLocations))

'Data Structure&Algorithm > Greedy' 카테고리의 다른 글

전자레인지 - [백준 10162번]  (0) 2021.07.14
세탁소 사장 동혁 - [백준 2720번]  (0) 2021.07.14
신입사원 - [백준 1946번]  (0) 2021.07.14
강의실 - [백준 1374번]  (0) 2021.07.14
배 - [백준 1092번]  (0) 2021.07.14
    'Data Structure&Algorithm/Greedy' 카테고리의 다른 글
    • 세탁소 사장 동혁 - [백준 2720번]
    • 신입사원 - [백준 1946번]
    • 강의실 - [백준 1374번]
    • 배 - [백준 1092번]

    티스토리툴바