반응형
https://www.acmicpc.net/problem/1439
알고리즘 분류: 그리디 알고리즘
💡코드 + 풀이
#1
s = list(input())
cnt0 = 0
cnt1 = 0
if s[0] == '0':
cnt0 += 1
else:
cnt1 += 1
for i in range(len(s)-1):
if s[i] != s[i+1]:
if s[i]=='0':
cnt1 += 1
else:
cnt0 += 1
else:
continue
print(min(cnt0, cnt1))
- 0으로 바뀌는 구간을 카운트하는 변수 cnt0와 1로 바뀌는 구간을 카운트하는 변수 cnt1을 각각 생성한다.
- 우선, 첫번째 문자만 확인 후, 0이면 cnt0에 1을, 1이면 cnt1에 1을 더해준다. (바뀌는 구간이 1번만 있을 때와 바뀌는 구간이 아예 없을 때를 구분하기 위해서이다.)
-
s cnt0 cnt1 최소 행동 (정답) 00 1 0 0 01 1 1 1
-
- 그리고 for문으로 전체 문자열을 돌면서 현재 문자가 다음 문자와 다를 때, 현재 문자가 0이면 0에서 1로 바뀐다는 뜻이므로 cnt1에 1을 더하고, 반대의 경우에는 cnt0에 1을 더한다.
- 최소 행동을 구하는 것이 문제의 정답이므로 cnt0과 cnt1 중 작은 수를 출력한다.
#2
s, change = input(), 0
for i in range(1, len(s)):
if s[i] != s[i-1]:
change += 1
print((change+1) // 2)
2번 풀이는 1번 풀이에서 규칙을 발견한 것을 적용하여 풀이한 것이다.
연속된 문자가 몇개 있는지는 관계없이 0에서 1로, 또는 1에서 0으로 바뀌는 구간이 몇개인지가 이 문제를 해결하는 데에서 중요하다.
s | 바뀌는 구간 | 최소 행동 (정답) |
0 또는 1 | 0 | 0 |
01 또는 10 | 1 | 1 |
010 또는 101 | 2 | 1 |
0101 또는 1010 | 3 | 2 |
01010 또는 10101 | 4 | 2 |
010101 또는 101010 | 5 | 3 |
0101010 또는 1010101 | 6 | 3 |
이렇게 연속된 문자는 생략한 채, 나타날 수 있는 경우를 차례대로 써보면 규칙이 잘 보인다.
최소 행동 = (바뀌는 구간 + 1) // 2로 나타날 수 있다.
이렇게 보여지는 규칙을 사용하면 위의 1번 풀이처럼 0에서 1로 1에서 0으로 바뀌는 구간을 따로 구분할 필요가 없다!
반응형
'Algorithm > BOJ' 카테고리의 다른 글
BAEKJOON #1449) 수리공 항승 (python) (0) | 2021.09.05 |
---|---|
BAEKJOON #1448) 삼각형 만들기 (python) (0) | 2021.09.05 |
BAEKJOON #11047) 동전 0 (python) (0) | 2021.09.04 |
BAEKJOON #11399) ATM (python) (0) | 2021.09.01 |
BAEKJOON #2839) 설탕 배달 (python) (0) | 2021.09.01 |
댓글