-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBank_03_Greedy.py
56 lines (48 loc) · 2.08 KB
/
Bank_03_Greedy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
## 무슨 유형인지 모르겠네.
## sub-problem으로 나눌 순 있는데,
## optimal sub-solution이 나오는지 모르겠음.
## 걍 글로벌하게 봐도 풀리는 것 같은데
## 양 끝만 보면 될 듯
## 양 끝이 다르면 뭐부터 뒤집나 상관 없는데,
## 양끝이 같으면, 양 끝이 아닌 다른 것을 뒤집어야 함.abs
## 제일 중요한 것은 몇 개의 뭉텅이인지 세는 건데.
## 걍 뒤집을 문자를 정하고, 뭉텅이 시작부분에서 카운트 올리자
###### 요 풀이는 막 푼거임 따지고보면.
# while(1):
# s = input()
# count = 0
# if s[0] == s[-1]:
# target_to_flip = ""
# if s[0] == "1":
# for i in range(len(s) - 1):
# if s[i] == "1" and s[i + 1] == "0":
# count += 1
# else:
# for i in range(len(s) - 1):
# if s[i] == "0" and s[i + 1] == "1":
# count += 1
# else:
# for i in range(len(s) - 1):
# if s[i] == "1" and s[i + 1] == "0":
# count += 1
# print(count)
###########################################
### 어느 지점에서 행동한다면 뒤의 원하는 지점까지 뒤집는거
### 구현 관점에서 보면, 행동 위치는 앞에서부터 보기 때문에
### 이러면 sub-problem으로 확실히 나눌 수 있음.(미래만 보는)
### 결국 최소한으로 행동하는 것이 목표니, sub-problem에서도,
### 안 뒤집을 수 있으면 안 뒤집는게 optimal
### 따라서 맨 앞에서 뒤집는 것은 안하게 됨.
###
### 중간 지점, 일반적인 상황에서 보게 되면,
### 항상 현재 보는 위치 왼쪽은 한 종류 숫자로 정렬 되어 있음.
### 이는 맨 첫번째 숫자랑 같은 종류임
### 따라서 앞에 나오는 숫자 종류가 다른 종류면 카운트
### 사실 진짜로 뒤집으면서 항상 자기 바로 이전 숫자랑 비교하는게 맞지만, 그러면 너무 복잡해지니까 간단하게 하려면 이렇게 하는게 맞다.
s = input()
my_num = s[0]
count = 0
for i in range(1, len(s)):
if s[i] != my_num and s[i - 1] == my_num:
count += 1
print(count)