백준 1449 , 1463

1. 백준 1449

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

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

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

def greed(lst,L):
    lst.sort()
    sum = 0
    cnt_start = 0
    cnt_end = 0
    while True:
        length = lst[cnt_end] - lst[cnt_start] + 1
        print("===")
        print(sum)
        print("st :", lst[cnt_start], " end : ", lst[cnt_end])


        if length <= L :
            sum +=0


            if cnt_end == len(lst) - 1:
                sum += 1
                break
            cnt_end += 1
        else:
            sum += 1

            if cnt_end == len(lst)-1:

                sum +=1
                break

            cnt_start = cnt_end



    return sum

if __name__ == '__main__':
    N = list(map(int, input().split()))
    lst = list(map(int, input().split()))

    print(greed(lst,N[1]))

** 8~10 line code 는 확인을 하기 위함 **

 

해당 문제는 Greed 알고리즘에 기반한다. 

 

먼저 해당 문제를 풀기 위하여 세운 알고리즘은 다음과 같다. 

 

1. start point 와 end point의 사이 length를 파악한다. (양 옆 0.5씩 차이가 나기 떄문에 +1 을 하여준다. 

2. 해당 length 가 L ( 테잎의 길이 ) 보다 낮을 시 end point 만 옆으로 옮겨준다.

3. 해당 length 가 L 보다 낮을 시 start point 를 endpoint 와 같이 두고 sum 을 1 더하여 준다. 

해당 과정을 반복한다. 

 

해당 알고리즘에서 취약한 부분은 물이 세는 마지막 파트를 어떻게 처리 할 것이냐 이다. 이를 해결하기 위해 각 조건에 따라 맞는 break 문을 추가 해 주었다. 

 

 

2. 백준 1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

 

n = int(input())

dp = [0 for _ in range(n + 1)]

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1

    if i % 2 == 0 and dp[i] > dp[i // 2] + 1:
        dp[i] = dp[i // 2] + 1

    if i % 3 == 0 and dp[i] > dp[i // 3] + 1:
        dp[i] = dp[i // 3] + 1

print(dp[n])

 

 

 

해당 문제는 dinamic programming 중 bottom up 에 해당하는 문제이다. 

따라서 해당 문제를 풀기 위한 점화식은 다음과 같다. 

dp[i] = min(dp[i-1] +1 , dp[i//2] +1 , dp[i//3]+1) 

 

해당 점화식을 적용하기 위해 bottom up 방식을 취한다.

bottom up 이란, 작은 단위의 문제를 해결하고 다시 작은 문제를 해결 하는 방법을 취하는 것이다. 해당 문제에서 bottom up을 적용하기 위해 배열과 비교문을 이용하였다. 

 

코드 중 비교문에서의 의미는 다음과 같다. 

"만약 -1 식을 적용한 값이 "/2" 를 적용 한 연산 횟수가 크다면, 해당 값을 재정의 한다."

예를 들어  dp[3]  는 dp[1] +1 과 dp[2]+1 이 비교되는데, dp[1] 은 0 , dp[2] = 1 이다. 따라서 dp[1]+1 < dp[2]+1 임으로 dp[3] = 1 로 가장 작은 값이 보장이 된다. 

 

** 주로 bottom up 은 배열을 통해 특정 값을 보장하는 방식으로 해결한다 **