[5문제] 그리디 문제풀이 04

백준 18238번

해결 아이디어

원판은 문자열을 기준으로 왼쪽 또는 오른쪽으로 돌릴 수 있으며, 두 가지 경우에서 이동 시간이 짧은 경로로만 문자를 출력하면 걸리는 시간의 최솟 값으로 문자열을 완성시킬 수 있다. 알파벳을 문자열로 만들어서 해결할 수도 있었지만, 아스키코드를 활용하였다. 그리고 차이가 음수일 경우 26(알파벳의 개수)을 더해주었다.

내가 작성한 코드

word = input()
start = 'A'
time = 0

for i in word:
    left = ord(start) - ord(i)
    right = ord(i) - ord(start)

    if left <= 0:
       left += 26

    elif right <= 0:
       right += 26

    time += min(left, right)
    start = i
    
print(time)

백준 18228번

해결 아이디어

펭귄이 얼음1 또는 N이 위치하는 경우는 존재하지 않으므로 결국에는 왼쪽, 오른쪽에서 펭귄을 떨어뜨릴 수 있는 최소 힘이 드는 얼음을 고르면 되는 간단한 문제였다.

하지만 본인은 입력을 꼼꼼히 읽지 않아서 펭귄이 얼음1 또는 N이 위치하는 경우까지 생각해서 오답을 받았었다. 문제 똑바로 읽자

내가 작성한 코드 - 오답

num = int(input())
ice = list(map(int,input().split(' ')))

png = ice.index(-1)
left = ice[png-1]
right = ice[png+1]


if png - 1 == 0:
    first_crush = left

elif png + 1 == num - 1:
    first_crush = right

else:
    first_crush = min(left,right)

if first_crush == left:
    second_crush = min(ice[png+1:])
    
elif first_crush == right:
    second_crush = min(ice[:png])

min_crush = first_crush + second_crush

print(min_crush)

내가 작성한 코드

num = int(input())
ice = list(map(int,input().split(' ')))

png = ice.index(-1)
min_power = min(ice[:png]) + min(ice[png+1:])
print(min_power)

백준 14471번

해결 아이디어

M-1개 이상의 경품을 가지려고 할 때, 경품을 얻기 위해서 필요한 비용이 최솟값이려면 M-1개의 경품을 가져야 한다. 경품과 교환할 수 있는 포인트카드는 제외하고, 경품으로 교환하지못하는 각 포인트카드의 경품으로 교환할 수 있는 비용을 리스트로 담는다. 그 리스트를 오름차순 정렬시킨 후, 더 받아야 하는 경품의 개수 전까지의 요소의 합을 구하도록 했다.(리스트 인덱스는 0부터 시작하므로)

내가 작성한 코드

N, M = map(int, input().split())
bomb = []
count = 0
for i in range(M):
    a, b = map(int, input().split())
    if a >= N:
        count +=1
    else:
        bomb.append(N - a)
if count >= M - 1:
    print(0)
else:
    bomb = sorted(bomb)
    rest_jackpot = (M - 1) - count
    cost = sum(bomb[:rest_jackpot])
    print(cost)

백준 2828번

해결 아이디어

1칸 차지하는 바구니일 경우에는 방법이 잘 떠올랐지만, 2칸이상을 차지하는 바구니일 경우에는 방법이 잘 떠오르지 않아서 타인의 풀이방법을 참고했던 문제이다. 바구니의 왼쪽 끝과 오른쪽 끝을 지정해주는 것이 포인트였던 것 같다.

코드

N, M = map(int,input().split())
j = int(input())
apple = [int(input()) for _ in range(j)]

distance = 0
start = 1
end = M

for i in range(j): 

    if end >= apple[i] and start <= apple[i]:
        continue

    elif end < apple[i]:
        distance += apple[i] - end
        end = apple[i]
        start = apple[i] - (M - 1)

    elif start > apple[i]:
        distance += start - apple[i]
        start = apple[i]
        end = apple[i] + (M - 1)

print(distance)

백준 14655번

해결 아이디어

항상 연속한 3개의 동전을 뒤집으며, 동전 배열의 양끝에서 벗어나서 양끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집기도 가능하고, 더군다나 동전을 뒤집는 횟수에도 제한이 없으니 욱제는 동전 배열의 모든 동전을 움직일 수 있는 것이 자명하다. 따라서 욱제가 획득할 점수는 1라운드,2라운드 동전 배열의 절댓값의 합이다.

내가 작성한 코드

num = int(input())
round_1 = list(map(int,input().split()))
round_2 =  list(map(int,input().split()))
result1 = 0
result2 = 0

for i in round_1:
    result1 += abs(i)
for i in round_2:
    result2 += abs(i)

result = result1 +result2
print(result)