코딩,안되면 될때까지

[백준 1449번-수리공 항승]-파이썬 본문

백준/백준-파이썬

[백준 1449번-수리공 항승]-파이썬

soo97 2022. 4. 19. 09:43
728x90
반응형

solved.ac 난이도 :  Silver3

백준 1449번- 파이썬 풀이

 

<문제>

https://www.acmicpc.net/problem/1449

 

1449번: 수리공 항승

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나

www.acmicpc.net

<풀이>-그리디알고리즘

우선 배열을 입력받은 다음 배열의 원소를 오름차순 정렬한다.

 

테이프의 길이를 m이라 할때 배열의 첫번째 원소를 start라 하고 다음 원소를 i라 할때 (i+0.5)-(start-0.5) r가 m 보다 작으면 continue, 크면 테이프의 갯수를 +1해준다

 

수리가 필요한 곳의 위치가 [1 2]이고 테이프의 길이가 2라고 해보자

 

0.5~1.5의 범위와 1.5~2.5의 범위를 다 막아주어야만 수리가 성공적으로 이루어진다. 테이프의 길이가 2 이므로 테이프를 한개만 사용해서 1 2의 위치를 전부 수리할 수 있다.

 

반면 [1 2 4] 를 살펴보자. 마찬가지로 테이프의 길이는 2라고 한다.

 

그렇다면 0.5~1.5, 1.5~2.5, 3.5~4.5의 범위를 각각 다 막아줘야한다. 테이프의 길이는 2이므로 [1 2]는 테이프 한개로 수리가 가능하지만 4의 위치를 막을 경우는 테이프를 하나 더 추가해줘야 한다. 

 

이러한 아이디어를 코드로 옮기면 다음과 같다.

728x90
반응형

<코드>-파이썬

 

n,m = map(int,input().split())
pipe = list(map(int,input().split()))
pipe.sort()

start = pipe[0]
count = 1

for i in pipe[1:]:
    if (i+0.5)-(start-0.5)<=m:
        continue
    else:
        start = i
        count+=1
print(count)

-마치며-

 

그리디 알고리즘 문제는 풀때마다 느끼는 거지만 다양한 풀이가 정말 많다. 그리고 우리가 수학 문제를 푸는 것처럼 문제를 보고 문제를 풀기위해 얼마나 좋은 아이디어를 떠올릴 수 있는지가 중요한거 같다. 때문에 문제를 정말 많이 풀어보고 다양한 풀이법을 접하는 것이 좋은 거 같다. 필자는 위와 같이 풀었지만 for문 안의 if문을 다음과 같이 구성할 수도 있다.

 

    if i in range(start,start+m):
        continue
728x90
반응형
Comments