[Algorithm] 백준 - 설탕 배달 (2839번)

문제

[백준] 설탕 배달
(Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번)

사용 알고리즘

 

- 동적계획법 (Dynamic Programming)

해결방법

• 동전으로 금액을 만드는 문제와 같다고 보면 된다. 
  • > 3과 5를 가지고 N키로 만들기
• $dp[N] = 사용한 최소 동전(설탕 봉지) 수
• $dp 배열을 0으로 초기화 해준 뒤 반복문을 돌면서 채워주면 되는데, 이 때 3, 5 번째는 각 각 1개의 봉지 만으로 만들 수 있기 때문에 1로 갱신, 4의 경우 만들 수 없는 숫자기 때문에 0으로 갱신해준다.
• $dp[$i-3], $dp[$i-5] 의 값이 모두 있는 경우 (0보다 큰 경우)
  • 최소 값에 1을 더해주면 된다.
• $dp[$i-3], $dp[$i-5] 중 하나만 값이 있는 경우,
  • 둘 중 하나는 0이므로 둘을 더 했을 때 0 이상의 값이면 해당 값에 +1을 해주면 되고, 아닌 경우 둘 다 갈 수 없는 경로란 의미이므로 0을 넣어준다

소스코드

사용언어 : php

<?
    fscanf(STDIN,"%d",$N);
    $dp = [];
    $dp = array_fill(0, $N, 0); // [돈] = 최소 동전수 
    
    $dp[3] = 1;
    $dp[4] = 0;
    $dp[5] = 1;

    for($i = 6; $i <= $N; $i++){
        if ($dp[$i-3] && $dp[$i-5]) {
            $dp[$i] = min($dp[$i-3], $dp[$i-5]) + 1;
        } else {
            $dp[$i] = ($dp[$i-3] + $dp[$i-5]) ? ($dp[$i-3] + $dp[$i-5]) + 1 : 0; 
        }
    }
    
    echo $dp[$N] ?: -1;
?>

php standard I/O

https://www.php.net/manual/en/features.commandline.io-streams.php

PHP: I/O streams - Manual

 

 

 

한줄평

백준엔 php 런타임이 있다! ㅠㅠ