알고리즘 유형별 기출문제: 그리디

💻 2. 곱하기 혹은 더하기

난이도🖤🤍🤍 | 풀이시간 20분 | 제한시간 2초 | 메모리제한 128MB | 핵심유형 https://www.acmicpc.net/problem/1439

---

https://velog.io/@eastgloss0330/%EB%B0%B1%EC%A4%801430-%EB%92%A4%EC%A7%91%EA%B8%B0Python

---

📌2021/01/02 작성 코드

# 입력
s = input()

# 연속된 0 덩이 수, 연속된 1 덩이 수 구하기
zero = 0
one = 0

prev = s[0]
if prev == '0':
    zero += 1
else:
    one += 1

for current in s[1:]:
    # 연속된 숫자임
    if current == prev:
        continue
    # 연속된 숫자가 아님
    else:
        if current == '0':
            zero += 1
        else:
            one += 1
        prev = current

# 연속된 덩이 수가 적은 것을 바꾸는 게 효율적
# 바꾸는 횟수는 덩이 수와 같다
if zero < one:
    print(zero)
else:
    print(one)

---

🤓 문제 해설

• 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산하면 된다.

---

🤓 답안 예시

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

# 첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

---

🤔 리뷰

• 간단하게 풀 수 있었다! 핵심은 전체 0의 개수, 전체 1의 개수가 아니라 0의 덩이 수, 1의 덩이 수!
• 백준에서 풀 수 있는 문제였기에 [백준]카테고리에도 글을 올려 놓았다.