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

solved.ac 난이도 :  Silver3

백준 1449번- 파이썬 풀이

 

<문제>

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

1449번: 수리공 항승

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

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

 

테이프의 길이를 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