-
1449. [Python]수리공 항승Python_알고리즘/Silver III 2023. 6. 14. 23:07
1. 문제
https://www.acmicpc.net/problem/1449
1449번: 수리공 항승
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 그리디 알고리즘
3. 파이썬 코드
N,L = map(int,input().split()) # 테이프 붙이는 위치 tape_list = list(map(int,input().split())) # 1000까지 존재하는 테이프 위치 tapes = [0]*1001 # 테이프를 붙인 위치 표시 for i in tape_list: tapes[i] = 1 # 테이프가 붙었을때 어디까지 붙여지는지 확인할 리스트 water = [0]*1001 # 테이프 길이가 정렬된 것이 아니기 때문애 정렬 tape_list.sort() # 테이프 갯수 cnt = 0 # 구멍의 개수 만큼 반복 for i in range(N): # 처음 테이프 위치 저장 tape = tape_list[i] # 만약 테이프가 안붙어 있는 경우 if water[tape] == 0: # 테이프를 붙이고 water[tape] = 1 # 테이프 길이 만큼 반복문 시행 for j in range(1,L): # 1씩 증가해 가며 1000을 넘으면 중지 if tape+j > 1000: break # 외의 경우 else: # 연속인지 확인하기 위해서 tape에 j 더했을 때 테이프를 붙여야 하는 곳이면 water에 1을 넣어서 붙였다고 표시 if tapes[tape+j] == 1: water[tape+j] = 1 # 테이프 갯수 증가 cnt += 1 print(cnt)
4. 문제를 풀고난 후 생각
- 리스트 두개를 사용하여 문제를 해결 하였다.
- 연속성이 있는 부분을 어떻게 해결할지 고민을 했고 입력이 1000 까지밖에 들어오지 않아서 리스트 두개를 생성하여 테이프를 붙여야 하는 리스트와 테이프가 붙어있는지 확인 하기 위한 리스트를 생성했다.
- 조금 복잡하더라도 테이프를 붙여야 하는 위치의 인덱스를 표시 한 후 테이프 길이 만큼 연속된 구간이 있으면 water 리스트에 1 을 넣어서 테이프를 붙인 것을 표기 했다.
- 이후 리스트의 다음 인덱스를 꺼내서 테이프가 붙었는지 아닌지 water를 통해서 확인 한 후 같은 반복 동작을 시행 했다.
- 테이프가 안붙어있어야 cnt(테이프 갯수)가 증가한다.
리스트가 정렬된 형태가 아닌 무작위로 들어 온다. 이를 고려하지 않고 코드를 구현 했다가 1%도 못가고 틀렸다. 꼭 테이프 리스트를 정렬부터 진행한 후 뽑아서 사용하자!! 정렬 안하면 순서 뒤죽박죽이라 거꾸로 갈 수도...
ex) 3 2
3 2 1
정렬 안하면 : 3
정렬 하면 : 2
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 정렬
'Python_알고리즘 > Silver III' 카테고리의 다른 글
2503. [Python]숫자 야구 (0) 2023.07.13 2597. [Python]줄자접기 (0) 2023.06.17 2346. [Python]풍선 터뜨리기 (2) 2023.06.13 2371. [Python]파일 구별하기 (1) 2023.06.11 1448. [Python]삼각형 만들기 (1) 2023.06.06