✅ 문제 풀이 - BOJ (Greedy)
🎈 2828 사과 담기 게임
스크린 n칸, 처음에는 왼쪽에서 n칸 중 m칸을 바구니가 차지하고 첫 줄에 n, m이 주어진다.
둘째 줄부터 떨어지는 사과 개수 j가 주어지고 j줄만큼 사과가 떨어지는 위치가 주어진다.게임을 진행하며 바구니를 왼쪽, 오른쪽으로 이동시킬 수 있고 가장 초기 바구니는 왼쪽 m칸을 차지하고 있다.
각 사과는 n칸 중 한 칸 상단에서 떨어지기 시작하며 바닥에 닿는 순간 사과를 담을 수 있을 때 바구니의 이동 거리의 최솟값을 구하는 문제
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
j = int(input())
left = 1
right = m
answer = 0
for _ in range(j):
apple = int(input())
if left <= apple and right >= apple:
continue
elif apple > right:
answer += (apple-right)
left += (apple-right)
right = apple
else:
answer += (left - apple)
right -= (left - apple)
left = apple
print(answer)< 풀이 과정 >
단순 구현 느낌의 문제로 다음 과정을 거쳐 구현하였다.
- 우선 스크린 칸 n, 바구니 초기 1~m 칸, 사과 수 j를 입력받는다. 그리고 바구니가 차지하는 칸의 범위를 나타내기 위해 left = 1, right = m으로 초기 변수를 설정한다.
- for문으로 j번 반복하며 사과의 위치 apple을 입력받는다.
- 그 이후 3가지 조건을 거쳐 구현한다.
- 주어진 바구니 범위 [1,m] 내 사과가 위치하면 continue
- 사과 위치가 바구니 기준 오른쪽보다 크다면, apple-right만큼 우측으로 이동
- 사과 위치가 바구니 기준 왼쪽보다 작다면 left - apple 만큼 좌측으로 이동
위 과정을 거쳐 최소 이동거리를 출력한다.
🎈 1052 물병
n개의 물병을 가지고 있고, 각 물병에는 물을 무한대로 부을 수 있다. 처음 모든 물병에는 물이 1리터씩 들어있다. 한 번에 K개의 물병을 옮길 수 있을 때 적절히 재분배해 k개를 넘지않으면서 비어있지 않는 물병을 만들고자 한다.
물은 다음과 같이 재분배한다.
같은 양의 물병 2개를 고르고 한 병으로 합친다.최종적으로 물병 개수 N과 옮길 수 있는 물병 개수 K가 주어질 때 상점에서 추가로 사야하는 물병 개수를 구하는 문제. (정답을 구할 수 없으면 -1을 출력)
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
answer = 0
while bin(n).count('1') > k:
n = n+1
answer += 1
print(answer)< 풀이 과정 >
주어진 n개의 물병에 몇 개의 물병을 더해야 2의 제곱수가 되는지 확인하면서 병 수를 늘리면 되는 문제.
병 수를 늘리는 과정에서 k개를 넘지 않는 것을 조건으로 정하였으므로 while문으로 조건을 걸어 반복을 해준다.
🎈 2138 전구와 스위치
N개의 스위치, 전구가 있고 각 전구의 상태는 on/off 중 하나의 상태만을 갖는다.
i번 스위치를 누르면 i-1, i, i+1의 전구 상태가 바뀔때, 원하는 전구 상태로 바꾸기 위해 몇번의 스위치를 눌러야 하는지 최솟값을 구하면 되는 문제
(0은 꺼진 상태, 1은 켜진 상태를 의미)
import sys
input = sys.stdin.readline
import copy
n = int(input())
state = list(map(int, input().rstrip()))
want = list(map(int, input().rstrip()))
def change_state(number):
if number == 0:
number = 1
else:
number = 0
return number
def switch(state, count):
# 첫 번째 전구인 경우 state배열의 0, 1번째 인덱스에 위치한 전구 상태 변환하기
if count == 1:
state[0] = change_state(state[0])
state[1] = change_state(state[1])
# 1부터 n까지는 반복
for i in range(1, n):
# 현 상태와 원하는 상태의 전구 상태가 다를 경우
if state[i-1] != want[i-1]:
# 스위치 버튼 누름 + 1처리 이후 i-1, i번쨰 현 전구 상태 변환
count += 1
state[i-1] = change_state(state[i-1])
state[i] = change_state(state[i])
# 끝 인덱스를 제외한 경우에 i+1번째 전구 상태 변환하기
if i != n-1:
state[i+1] = change_state(state[i+1])
# 현 전구 상태가 원하는 전구 상태가 되었다면 idx 리턴, 아니면 -1
if state == want:
return count
else:
return -1
push_first = copy.deepcopy(state)
push_first = switch(push_first, 0)
not_push_first = copy.deepcopy(state)
not_push_first = switch(not_push_first, 1)
if not_push_first >= 0 and push_first >= 0:
print(min(not_push_first, push_first))
elif not_push_first >= 0 and push_first < 0:
print(not_push_first)
elif not_push_first < 0 and push_first >= 0:
print(push_first)
else:
print(-1)< 풀이 과정 >
현 전구 상태를 state, 원하는 전구 상태를 want라고 둘 때, 문제의 핵심은 i번째 스위치를 정하는 기준이다.
주어진 배열의 앞부터 스위치를 눌러가며 바꾸어야 하는지 확인하는 방법으로만 스위치를 누르는 최소 횟수를 구할 수 있다. 그 과정은 다음과 같다.
- change_state 함수로 주어진 number를 0이면 1로, 1이면 0으로 바꿔준 후 리턴한다.
- switch함수로 state와 count(스위치 누르는 횟수)를 입력받아 첫 전구부터 스위칭 처리를 해준다. 주어진 배열 범위 내에 i-1, i, i+1 번째 전구 상태를 change_state로 변환한다.
- 최종적으로 첫 전구가 위치한 스위치를 누르냐 안누르냐 두가지 상태를 비교하여 -1이 아닌 경우를 채택해 출력하면 되는 문제
🎇 참고사항
shallow copy : 새로운 객체를 생성하지만 원본에 접근가능 (원본 객체의 주소값만 복사)
deepcopy : 완전한 독립적인 객체를 만들기 위해서 필요 (객체 자체를 완전복사)
좀 더 자세히 코드로 살펴보면 다음과 같다.
import copy
a = [1, [1, 2, 3]]
# 얕은 복사
b = copy(a)
# 깊은 복사
c = copy.deepcopy(a)
id(a), id(b), id(c)
# (4592854280, 4591051528, 4594252744)
# 일단 모든 객체는 서로 다른 주소를 가진다
id(a[1]), id(b[1]), id(c[1])
# (4592595592, 4592595592, 4594187592)
# 얕은 복사한 b의 내부 리스트는 원본과 같은 주소를 가진다
# 그렇기 때문에 원본에 영향을 받는 것이다