16498.md

백준 16498번 작은 벌점

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

---

코드 설명

• start와 end를 0으로 초기화해 인덱스 0부터 구간들을 살펴 나가는 방식으로 구현한다.
• 여기서 구간 안에는 무조건 a, b, c의 카드가 한 개 이상은 포함되어야 한다. -> 이 조건을 로직으로 구현하기 위해 각 카드의 개수를 생각하는 방식으로 구현
• start와 end의 차이를 이해해야 한다. -> start는 범위를 좁혀 나가기 때문에 카드 개수를 빼주는 식으로 해야 구현해야 하고, end는 범위를 넓혀 나가기 때문에 카드 개수를 늘리는 방식으로 구현해야 한다.

소스코드

• 메모리 : 30864 KB
• 시간 : 76 ms

import sys

a, b, c = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
lst = []
result = []

for aa in A:
    lst.append([aa,'a'])
for bb in B:
    lst.append([bb,'b'])
for cc in C:
    lst.append([cc,'c'])
    
lst.sort()
start, end = 0, 0
acnt, bcnt, ccnt = 0, 0, 0
while 1:
    if end >= len(lst):
        if acnt >= 1 and bcnt >= 1 and ccnt >= 1:
            result.append(lst[end-1][0]-lst[start][0])
        break
    if acnt >= 1 and bcnt >= 1 and ccnt >= 1:
        result.append(lst[end-1][0]-lst[start][0])
        if lst[start][1] == 'a': acnt -= 1
        if lst[start][1] == 'b': bcnt -= 1
        if lst[start][1] == 'c': ccnt -= 1
        start += 1
    else:
        if lst[end][1] == 'a': acnt += 1
        if lst[end][1] == 'b': bcnt += 1
        if lst[end][1] == 'c': ccnt += 1
        end += 1
        
print(min(result))

오답 노트

• start와 end 의 값을 바꾸면서 인덱스 범위를 좁혀 나가는 식으로 했는데 코드를 잘못 짜 충분히 범위를 줄이기도 전에 반복문을 빠져나와 버리게 되었다. -> 이 부분 수정
• 초반에는 start와 end를 각 0과 리스트 끝의 -1 인덱스 위치에서 시작해 좁혀 나가는 방식으로 구현을 시도했다. 이럴 경우 문제점이 만약 작은 벌점 구간을 지나칠 수도 있단 점이다.
  -> 초반에 구현한 방법은 앞 뒤로 범위를 줄이기 때문에 구간이 가운데 위치하면 상관없으나 앞쪽에 위치할 경우에는 end가 뒤쪽에 있기 때문에 고려하지 못한다는 단점이 있었다.
• start와 end로 인덱스 위치를 지정해 범위를 좁혀 나가는 시도는 좋았다. 다만 보다 로직을 더 생각해야 한다.

오답 코드

import sys

a, b, c = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
lst = []
result = []

for aa in A:
	lst.append([aa,'a'])
for bb in B:
	lst.append([bb,'b'])
for cc in C:
	lst.append([cc,'c'])
	
lst.sort()
start = 0
end = len(lst)-1

while a != 0 and b != 0 and c != 0:
	result.append(lst[end][0]-lst[start][0])
	if lst[end][1] == 'a': a -= 1
	elif lst[end][1] == 'b': b -= 1
	elif lst[end][1] == 'c': c -= 1
	end -= 1
	if a == 0 or b == 0 or c == 0: break
	result.append(lst[end][0]-lst[start][0])
	if lst[start][1] == 'a': a -= 1
	elif lst[start][1] == 'b': b -= 1
	elif lst[start][1] == 'c': c -= 1
	start += 1
	if a == 0 or b == 0 or c == 0: break
	
print(result[-1])