Greedy

Q.11399

ATM

소요시간을 오름차순으로 정렬
n=5라고 하면 0번 인덱스는 5번 더해지고, 1번 인덱스는 4번 더해지고,,, 즉 (n-idx) * time[idx]로 구현할 수 있다.

n = int(input())
array = list(map(int, input().split()))
array.sort()
result = 0

for i in range(n):
    result += (n-i) * array[i]
    
print(result)

---

Q.2839

설탕 배달

5로 나누어지면 그 몫을 result에 더하기, 안 나눠지면 5로 나눠질때까지 3을 빼기

n = int(input())
result = 0

while True:
    if n < 3:
        result = -1
        break
    else:
        if n % 5 == 0:
            result += n // 5
            break
        else:
            n -= 3
            result += 1
            if n == 0:
                break

print(result)

통과는 했지만 조건문 더 적게 쓰도록 수정해보자!

n = int(input())
result = 0

while n >= 3:
    if n % 5 == 0:
        result += n // 5
        break
    else:
        n -= 3
        result += 1
        if n == 0:
            break
else:
    result = -1
    
print(result)

위처럼 풀었더니 36ms가 되었다.
코드를 더 짧게 쓸 수 있을 것 같다. 바꿔보자!

최종

n = int(input())
result = 0

while n >= 0:
    if n % 5 == 0:
        result += n // 5
        break
    n -= 3
    result += 1
else:
    result = -1
    
print(result)

위처럼 수정했다. 시간과 메모리는 두 번째와 동일하게 나왔다.

---

Q.11047

동전 0

from bisect import bisect_right

n, k = map(int, input().split())
coins = []
result = 0

for _ in range(n):
    coins.append(int(input()))
    
not_use_idx = bisect_right(coins, k)

for x in range(not_use_idx-1, -1, -1):
    result += k // coins[x]
    k %= coins[x]
    if k == 0:
        break

print(result)

---

구현

Q.1316

그룹 단어 체커

풀이 1

n = int(input())
words = []
result = 0

for i in range(n):
    word = list(input())
    words.append(word)
    
for word in words:
    alp = []
    alp.append(word[0])
    check = 1
    
    for i in range(1, len(word)):
        if word[i] == word[i-1]:
            continue
        
        if word[i] in alp:
            check = 0
            break
        else:
            alp.append(word[i])
        
    if check == 1:
        result += 1
    
print(result)

풀이 2

n = int(input())
words = []
result = 0

for i in range(n):
    word = list(input())
    words.append(word)
    
for word in words:
    alphabets = [False] * 26
    alphabets[ord(word[0]) - ord('a')] = True
    check = True
    
    for i in range(1, len(word)):
        if word[i-1] != word[i]:
            if alphabets[ord(word[i]) - ord('a')]:
                check = False
                break
            alphabets[ord(word[i]) - ord('a')] = True
            
    if check:
        result += 1
    
print(result)

---

DP

Q.12852

1로 만들기 2

테스트케이스 다 맞게 나오는데 제출해보니 틀렸다... 이유를 알려줘ㅠㅠ

n = int(input())
dp = [0] * (n+1)
result = []

for i in range(2, n+1):
    if i % 3 == 0:
        dp[i] = dp[i // 3] + 1
    elif i % 2 == 0:
        dp[i] = 1 + min(dp[i // 2], dp[i - 1])
    else:
        dp[i] = 1 + dp[i - 1]

print(dp[n])

while True:
    result.append(n)
    if n == 1:
        break
    if n % 3 == 0:
        n //= 3
    elif n % 2 == 0:
        if dp[n // 2] > dp[n - 1]:
            n -= 1
        else:
            n //= 2
    else:
        n -= 1

print(*result)