2616번 - 소형기관차(dp)
문제: 풀이:각 소형 기관차가 끌 수 있는 객차 수를 3칸이라고 하자.객차의 수는 12개로 각 객차에 타있는 손님 수는 35, 40, 50, 10, 30, 45, 60, 20, 10, 50, 40, 70 이다.그렇다면 아래와 같은 전제를 도출할 수 있을 것이다.각 소형 기관차가 끌 수 있는 최대 인원은 연속되는 객차 3개의 인원의 합이다.고로 1~3번째 객차, 2~4번째 객차....10~12번째 객차만 고려하면 된다.두 소형 기관차가 끌 수 있는 최대 인원은 객차 6개의 인원의 합이다.고로 1~6번째 객차, 2~7번째 객차....7~12번째 객차만 고려하면 된다. 모든 소형 기관차가 끌 수 있는 최대 인원은 객차 9개의 합이다.고로 1~9번째 객차, 2~10번째 객차....4~12번째 객차만 고려하면 된..
2024. 8. 19.
