-
1449. [Python]수리공 항승Python_알고리즘/Silver III 2023. 6. 14. 23:07
1. 문제
https://www.acmicpc.net/problem/1449
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