1475번: 방 번호
첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 키 포인트는 9와 6이 서로 뒤집을 수 있다는 것입니다. 그 숫자들을 제외하고는 숫자의 개수만큼 세트의 개수가 증가하기 때문에 고려하기 쉽습니다. 따라서 0부터 9까지 0으로 초기화된 리스트를 선언하고 6, 9는 더 작은 인덱스 번째를 증가시켜주고 그 외의 숫자는 해당 인덱스의 값을 증가시켜주는 방법을 통하면 쉽게 계산할 수 있습니다.
35996가 입력으로 주어진다고 가정하면 3번째 인덱스 5번째 인덱스의 값을 각각 증가시킵니다. 이를 그림으로 표현하면 다음과 같습니다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
초기 상태
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
3번째와 5번째를 하나씩 증가시킨 후
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 인덱스를 증가시킴 편의상 낮은 인덱스를 증가시킴
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 9번째 인덱스를 증가시킴
| 0 | 0 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 1 |
6이 왔으므로 6번째 인덱스와 9번째 인덱스 중 더 작은 값을 가지는 6번째 인덱스를 증가시킴
이렇게 각 인덱스를 증가시키는 과정이 끝난 후 리스트에서 최댓값을 출력하면 필요한 세트의 수가 나오는 것을 알 수 있다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
word = input()
ans = [0] * 10
for i in range(len(word)):
num = int(word[i])
if num == 6 or num == 9:
if ans[6] <= ans[9]:
ans[6] += 1
else:
ans[9] += 1
else:
ans[num] += 1
print(max(ans))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14503: 로봇 청소기(Python) (0) | 2021.02.03 |
|---|---|
| 백준 알고리즘 10773: 제로(Python) (0) | 2021.02.03 |
| 백준 알고리즘 7568: 덩치(Python) (0) | 2021.02.03 |
| 백준 알고리즘 1966: 프린터 큐(Python) (0) | 2021.02.02 |
| 백준 알고리즘 1316: 그룹 단어 체커(Python) (0) | 2021.02.02 |