이코테 유형별 기출문제

그리디

문자열 뒤집기

풀이특징

• 앞, 뒤 숫자가 다른 경우 카운트 증가

# 모든 숫자가 같도록 뒤집는 최소횟수
nums = input()
zeroCount = 0
oneCount = 0
if nums[0] == '0':
    zeroCount += 1
else:
    oneCount += 1

for i in range(len(nums)-1):
    if nums[i] != nums[i+1]:
        # 횟수 증가
        if nums[i+1] == '0':
            zeroCount += 1
        else:
            oneCount += 1

print(min(zeroCount, oneCount))

만들 수 없는 금액

풀이 특징

• 현재까지 만들 수 있는 금액을 target-1 라고 가정
• target 금액을 현재 coin 으로 만들 수 있는지 비교
• 만들 수 있다면 target += coin 업데이트 (target-1 금액에 coin 더한금액들 모두 만들 수 있음)
• 아닌 경우 해당 target 금액 반환

# 만들 수 없는 최솟값
n = int(input())
coins = list(map(int, input().split()))
coins.sort()
# 1 1 2 3 9
target = 1
for coin in coins:
    if coin <= target:
        target += coin
    else:
        break

print(target)

볼링공 고르기

풀이 특징

• 무게별 공 개수 확인 필요
• 무게 오름차순으로 돌면서 A 선택, B의 경우 더 큰 무게의 공 개수(n - A선택까지의 공개수) 곱한 값 합산

# 두 사람이 서로 다른 무게의 공을 고르는 경우의 수
n, m = map(int, input().split())
balls = list(map(int, input().split()))
count = [0] * (m+1)
for ball in balls:
    count[ball] += 1

result = 0
for i in range(1, m):
    if count[i] == 0:
        continue
    first = count[i]
    second = n - count[i]
    result += (first * second)
    n -= count[i]

print(result)