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

백준 15904번

해결 아이디어

체크리스트에 'U','C','P','C'를 담아놓고 인덱스로 문자열을 확인했다. 문자열 중에 체크리스트 요소가 확인되면 문자열 슬라이싱을 통해서 확인된 요소를 제외하고 끝까지 확인하는 작업을 거쳤다.

처음에는 for문을 통해서 문자열을 돌리고 'U','C','P','C'가 있을 경우 리스트에 담는 방법을 생각해서 문제를 접근했다. 출력 값은 같았지만, 오답 판정을 받았다. 코드를 확인해보니 출력과정이 얼렁뚱땅 넘어가는 느낌이었고, 반례들이 있다는 것도 확인할 수 있었다.

내가 작성한 코드 - 오답

words = input()
ucpc= []

for i in words:
    if i == 'U':
        ucpc.append(i)
    elif i == 'C':
        ucpc.append(i)
    elif i == 'P':
        ucpc.append(i)

ucpc = ''.join(ucpc)

if ucpc == 'UCPC':
    print('I love UCPC')
else:
    print('I hate UCPC')

내가 작성한 코드

words = input()
checklist= ['U','C','P','C']

count = 0
for i in checklist:
    if i in words:
        count +=1
        idx = words.index(i)
        words = words[idx + 1:]
if count == 4:
    print('I love UCPC')
else:
    print('I hate UCPC')

백준 1343번

해결 아이디어

replace함수를 사용했다. replace함수는 문자열 왼쪽부터 찾아서 치환해주기 때문이다. 'XXXX'를 'AAAA'로 대신해주고, 'XX'를 'BB'로 대신해주도록 했다. 다 돌렸을 때, 'X'가 보드판에 남아있다면 다 덮을 수 없는 보드판이므로 -1을 출력한다.

처음 문제를 접할 때는 .의 존재로 인해 문자열에서 'X'가'.'으로 바뀌는 방법으로 접근하면서 사전순으로 가장 앞서는 답을 출력해야하는 조건까지 고려해야하니 점점 복잡해졌다. 오랜 생각 끝에 파이썬에서 문제를 단순화시킬 수 있는 도구인 replace 함수를 떠올릴 수 있었다.

내가 작성한 코드

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

if 'X' in board:
    print(-1)
else:
    print(board)

백준 9237번

해결 아이디어

나무들이 자라는 시간을 최소화시키려면 자라는 시간이 가장 오래 걸리는 나무를 먼저 심어야한다. 각 그루 당 심은 날, 심는데 걸리는 시간 1일, 자라는 시간을 합해준다. 그 중에서 최댓값이 모든 나무가 다 자라는 시간이자 나무들이 가장 빠르게 자라는 시간이다. 이장님은 마지막 나무가 다 자란 다음날 초대하므로 1을 더해준다.

내가 작성한 코드

n = int(input())
tree_days = list(map(int,input().split(' ')))
tree_days = sorted(tree_days, reverse = True)

for i in range(n):
    tree_days[i] = tree_days[i] + i + 1

print(max(tree_days)+1)

백준 16435번

해결 아이디어

스네이크버드가 최대 길이가 되려면 최대한 과일을 많이 먹어야 한다. 자신의 길이보다 작거나 같은 높이에 있는 과일을 먹을 수 있으므로, 높이 h를 리스트로 받아 내림차순 해준다. for문을 돌려서 과일을 먹게 해주고 높이가 스네이크버드의 길이보다 높을 경우의 조건을 걸어 break으로 빠져나오게 해준다.

내가 작성한 코드

n , l = map(int, input().split(' '))
h = list(map(int, input().split(' ')))
h = sorted(h)

for i in h:
    if l >= i:
        l+=1
    else:
        break

print(l)

백준 19939번

해결 아이디어

서로 다른 공의 개수를 담은 바구니이므로 최소한 N은 1부터 K까지의 합만큼 공의 개수를 가지고 있어야 한다. N이 그 값보다 작을 경우, 서로 다른 공의 개수로 바구니에 공을 담을 수 없으므로 -1을 출력해준다. 1부터 K까지의 합으로 바구니에 공을 분배한 후, 공이 남았을 때를 생각해보자.

바구니의 개수가 남은 공의 개수로 나누어 떨어진다면, 바구니에 균등하게 공을 넣어주면 된다. 그렇다면 가장 적은 공 개수를 가지고 있는 바구니(1)에서 가장 많은 공 개수를 가지고 있는 바구니(K)를 빼준 값인 K-1을 출력해주면 된다.

바구니의 개수가 남은 공의 개수로 나누어 떨어지지 않는다면, 공의 개수 차이를 최소로 만들기 위해서 가장 많이 담긴 바구니부터 거꾸로 남은 공을 넣어준다. 그렇다면 가장 적은 공 개수를 가지고 있는 바구니(1)에서 가장 많은 공 개수를 가지고 있는 바구니(K+1)를 빼준 값인 K를 출력해주면 된다.

내가 작성한 코드

n, k = map(int,input().split(' '))
ball_min = k*(k+1)/2

if n < ball_min:
    print(-1)

elif (n - ball_min) % k == 0:
    print(k-1)

else:
    print(k)		# (k-1) - 1