백준 greedy 실버5 모음1 - 파이썬

 

[1343] 폴리오미노(실버5)

# 흐름대로 푼 풀이
import sys
input = sys.stdin.readline

board = input().strip().split('.') 
str = ''

while(len(board) != 0):
  b = board.pop(0)
  if len(b) % 2 != 0:    # X 개수가 홀수면 -1출력
    str = '-1'
    break

  countA = len(b)//4
  countB = (len(b)%4)//2
  str += 'AAAA'*countA
  str += 'BB'*countB
  if len(board) != 0:
    str += '.'

print(str)

# 간단한 풀이
import sys
input = sys.stdin.readline

board = input().strip()
board = board.replace('XXXX', 'AAAA')
board = board.replace('XX', 'BB')

if 'X' in board:
  board = '-1'

print(board)

 

문자열 관련 함수인 replace는 왼쪽부터 해당하는 문자열 찾아서 치환해줌. 

믄자열이니까 replace로 푸는게 더 간단한 것 같다. 

 

 

[1417] 국회의원 선거(실버5)

# sort를 사용한 방법
import sys
input = sys.stdin.readline

candidatesNum = int(input().strip())
count = [int(input().strip()) for _ in range(candidatesNum)]
dasom = count.pop(0)

result = 0

if len(count) != 0: # 후보가 한 명이 아닐 경우
  count.sort(reverse=True)

  while dasom <= count[0]:
    result += 1
    dasom += 1
    count[0] -= 1
    count.sort(reverse=True)

print(result)

# 최대 힙을 사용한 방법
import heapq

candidatesNum = int(input())
dasom = int(input())
count = []
for _ in range(candidatesNum-1):
    heapq.heappush(count, -int(input()))

result = 0

if len(count) != 0: # 후보가 한 명이 아닐 경우
  while True:
      maxVote = -heapq.heappop(count)
      if dasom > maxVote:
          break
      result += 1
      dasom += 1
      heapq.heappush(count, -(maxVote-1))

print(result)

 

• sort()나 최대힙 둘 중 하나를 사용하면 쉽게 풀 수 있다.
• 투표 수 값의 최댓값보다 다솜이의 투표 수를 비교하고, 다솜이가 작으면
• 다솜이투표수 += 1,  투표수최댓값 -= 1
• 하여 최대힙에 넣어주거나 sort하는 걸 반복하면 된다. 

 

 

[1439] 뒤집기(실버5)

import sys
input = sys.stdin.readline

string = input().strip()

arr = []
arr.append(sum([1 if len(c) != 0 else 0 for c in string.split('1')]))
arr.append(sum([1 if len(c) != 0 else 0 for c in string.split('0')]))

print(min(arr))

 

• 2가지 케이스에 대해 뒤집은 수를 구하여 최솟값을 출력한다.

1. 연속한 0 뒤집기
2. 연속한 1 뒤집기

 

# 더 간단한 물이
import sys
input = sys.stdin.readline

string = input().strip()

change = 0
prev = -1
for s in string:
  if prev != s:
    change += 1
    prev = s

print(change//2)

 

• 변화 횟수를 구하여 정답을 구한다.
• (변화횟수+1) // 2   가 정답이다.

이해를 돕기 휘한 설명

 

 

[1789] 수들의 합(실버5)

import sys
import math
input = sys.stdin.readline

S = int(input().strip())

print(math.floor(((1 + 8 * S)** 0.5 - 1)/2))

 

• 등차수열 합 공식과 근의 공식을 이용했다.
• N이 최대가 되려면 S보다 작은 1부터 연속된 값의 합과 개수를 구하면 된다. 예를 들면
  S=8: 1+2+3이 가장 작은 1부터 연속된 값이고, N이 최대가 되려면 1+2+5로 만들어야함. 
  S=9: 1+2+3이 가장 작은 1부터 연속된 값이고, N이 최대가 되려면 1+2+6로 만들어야함.
  S=20: 1+2+3+4+5 이 가장 작은 1부터 연속된 값이고, N이 최대가 되려면 1+2+3+4+10으로 만들어야함.
• 그냥 S보다 작은 1부터 연속된 값의 최대 합을 구하면 거기포함된 자연수 개수가 최댓값인 N임.

• 등차수열 합 공식에 대입해주면 된다.
• N: 등차수열 수의 개수
• 1+2+3 이라면 3(1+3)//2 가 되니까 끝값이랑 N이 같아서 저런 공식이 나온다.

 

 

[1817] 짐 챙기는 숌(실버5)

import sys
input = sys.stdin.readline

bookNum, maxWeight = map(int, input().strip().split())

if bookNum == 0:
  print('0')
else:
  box = [0]
  idx = 0

  weights = list(map(int, input().strip().split()))

  for w in weights:
    if box[idx] + w > maxWeight:
      idx+=1
      box.append(0)

    box[idx] += w

  print(len(box))

1. 책 개수가 0이라면 0을 출력
2. box배열을 만들고 weights를 돌면서 책을 하나씩 담는다.
3. 담은 책 무게가 maxWeight를 넘으면 idx를 1 증가시키고 다음 박스에 담음
4. 만들어진 박스 개수를 출력 len(box)

 

 

[2057] 팩토리얼 분해(실버5)

import sys
input = sys.stdin.readline

N = int(input().strip())

if N == 0:
  print('NO')
else:
  facs = [1, 1]     # 팩토리얼 모음. 0! 1! 이 포함됨
  s = 2             # 2부터 시작
  while facs[-1] * s <= N:    # N보다 작은 팩토리얼 값들 찾기
    facs.append(facs[-1]*s)
    s += 1

  for f in facs[::-1]:        # 팩토리얼 최댓값부터 N에서 빼기
    N = N-f if N-f >= 0 else N
    if N== 0:
      break

  print('YES' if N == 0 else 'NO')      # N이 0이면 덧셈으로 나타낼 수 있다.

 

• N보다 작은 팩토리얼 값들을 모두 구해서 facs 배열에 담는다
• facs배열 최댓값부터 N이 음수가 되지 않게 값들을 빼준다.
• 마지막에 N이 0이 되었다면 팩토리얼들의 합으로 나타낼 수 있다.

# 가독성 좋은 버전
import sys
input = sys.stdin.readline

def factorial(n):
  if n == 0:
    return 1
  else:
    return n*factorial(n-1)

N = int(input().strip())

if N == 0:		# 0! = 1
  print('NO')
else:
  facs = [factorial(i) for i in range(21)]   # 팩토리얼 모두 담기

  for f in facs[::-1]:        # 팩토리얼 최댓값부터 N에서 빼기
    N = N-f if N-f >= 0 else N
    if N== 0:
      break

  print('YES' if N == 0 else 'NO')      # N이 0이면 덧셈으로 나타낼 수 있다.

• 팩토리얼 함수를 만들어서 가독성을 높임
• 최댓값이 21!보다 작기때문에 21개만 배열에 담으면 됨. 
• N이 0이 되면 덧셈으로 나타낼 수 있는 것

 

 

[2828] 사과 담기 게임(실버5)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
appleNum = int(input().strip())

loc = [int(input().strip()) for _ in range(appleNum)]

left = 1
right = M
distance = 0

for l in loc:
  if l < left:
    distance += (left - l)
    left -= (left - l)
    right = left + M-1
  elif l > right:
    distance += (l-right)
    left += (l-right)
    right = left + M-1

print(distance)

 

• 바구니의 왼쪽과 오른쪽 좌표를 저장해서 최소로 움직이도록 한다.
• right -= (left -1) 이러면 틀리고 right = left + M-1 이건 맞다고 나온다;; 무슨 차이인지 모르겠음

 

 

[2891] 카약과 강풍(실버5)

https://www.acmicpc.net/problem/2891

import sys
input = sys.stdin.readline

# 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R
N, S, R = map(int, input().strip().split())
damages = list(map(int, input().strip().split()))
extra = list(map(int, input().strip().split()))

team = [1]*N

for d in damages:
  team[d-1] -= 1

for e in extra:
  team[e-1] += 1

team.insert(0, -1)
team.append(-1)

for i in range(1, len(team)-1):
  if team[i] == 0:
    if team[i-1] == 2:
      team[i-1] = 1
      team[i] = 1
    elif team[i+1] == 2:
      team[i+1] = 1
      team[i] = 1

print(team.count(0))

 

1. 팀의 수만큼 1의 배열을 만들어준다. team[]
2. 손상된 카약의 인덱스에는 -1을 해주고 여분이 있는 카약의 인덱스에는 +1을 해준다. 나중에 값이 0인 개수를 세기 위해서이다.
3. 편의를 위해 team배열 맨 앞과 맨 뒤에 -1을 붙여준다. [-1, 1,2,0,1, -1] 이런식으로 만듦.
4. 인덱스 1부터 len(team)-1까지 반복해준다. 앞 인덱스[i-1]부터 확인하여 값이 2라면 하나를 가져오고, 앞 인덱스가 2가 아니라면 뒤 인덱스[i+1]를 확인하여 2라면 하나를 가져온다.
5. team배열 중 0의 수를 print

# 풀이2 전부 담지 않아도 풀 수 있음
import sys
input = sys.stdin.readline

# 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R
input()
damages = list(map(int, input().strip().split()))
extra = list(map(int, input().strip().split()))

result = 0

for d in range(damages):
  if d-1 in extra:
    extra.remove(d-1)
  elif d+1 in extra:
    extra.remove(d+1)
  else:
    result += 1

print(result)

 

그냥 damages랑 extra 배열로 찾으면 더 간단하다. 

 

 

[3135] 라디오(실버5)

import sys
input = sys.stdin.readline

A, B = map(int, input().strip().split())
N = int(input().strip())
bookmark = [int(input().strip()) for _ in range(N)]

minClick = abs(B-A)

for b in bookmark:
  if minClick > abs(B-b) + 1:    # 버튼을 한 번 눌렀으니까 +1
    minClick = abs(B-b) + 1

print(minClick)

 

1. 최소 클릭 수 minClick 에 B-A의 절댓값을 넣음(즐겨찾기 기능을 사용하지 않았을 때 클릭 수)
2. 즐겨찾기 주파수와 B의 차이의 절댓값을 구하고 minClick보다 작으면 minClick을 갱신
3. minClick 출력
4.  

import sys
input = sys.stdin.readline

A, B = map(int, input().strip().split())
N = int(input().strip())
bookmark = [int(input().strip()) for _ in range(N)]

clicks = [abs(B-b)+1 for b in bookmark]

print(min(abs(B-A), min(clicks)))

 

좀 더 짧은 풀이