반응형
문제
https://www.acmicpc.net/problem/1449
1449번: 수리공 항승
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나
www.acmicpc.net
풀이
그리디 알고리즘으로 풀이할 수 있습니다.
파이프의 길이는 최대 1000이므로,
1부터 1000까지 확인하면서 물이 세는 곳이라면,
길이가 L인 테이프를 붙여주어야 합니다.
그렇다면 물이 세는곳 + L 까지는 모두 테이프로 막아져있기 때문에,
물이 세는곳 + L부터 1000까지 다시 물이 세는곳을 확인해주고, 테이프의 수를 하나 늘려줍시다.
최대 1000까지 확인하였다면, 사용한 테이프를 출력해주면 됩니다.
소스코드
후기
물이 세는 곳을 만난다면 바로 테이프를 붙혀서 테이프의 길이 만큼은 전부 물이 세는 곳을 막아주기 때문에
그리디 알고리즘이란 것을 떠올려서 풀면 쉽게 풀 수 있습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 9184 신나는 함수 실행 (Swift) (0) | 2023.04.05 |
|---|---|
| [BOJ] 백준 24416 알고리즘 수업 - 피보나치 수 1 (Swift) (0) | 2023.04.05 |
| [BOJ] 백준 14889 스타트와 링크 (Swift) (0) | 2023.04.05 |
| [BOJ] 백준 14888 연산자 끼워넣기 (Swift) (0) | 2023.04.05 |
| [BOJ] 백준 2580 스도쿠 (Swift) (0) | 2023.04.05 |
