백준 2409 - 파이프 자르기

cl2380·2026년 4월 20일
백준

백준 문제풀이

목록 보기
37/37

문제 정보

문제 정리

M개의 긴 파이프를 잘라 N개의 짧은 파이프를 최대한 많이 만들려고 할 때, 만들 수 있는 파이프의 최대 개수를 구하는 문제이다.

문제 배경 관련

  • 구글 검색을 좀 많이 한 문제이다. 백준 출처에 따르면 이 문제가 USACO 1999 Spring 문제라고는 하는데, 너무 오래되어 USACO 공식 홈페이지에서 관련 자료를 찾을 수 없었다.
  • 검색을 하다 보니, "파이프 자르기" 문제의 영어 원본 문제는 "Fence Rails"는 "USACO Training Problems" 라는 문제 모음집에 수록되어 있었다.
    • 이 문제들은 https://usaco.training/ 해당 링크에서 회원가입을 하고 연습을 해볼 수 있다고 한다. (안해봐서 ㅁㄹ)
    • 좀 더 찾아 보니 이 사이트에 위 USACO Training Problems의 문제가 다 모아져 있었기에 굳이 저 사이트에 회원가입을 하지 않았다. 이 모음집의 Chapter 4 - Section 4.1.3을 보면 Fence Rails라는 문제를 확인할 수 있다.
    • 어떤 깃허브에 USACO Training Problems의 문제와 테스트케이스, 해결 코드가 올라와 있어 링크를 첨부해 둔다.
      • 이 깃허브의 Section 6.3에서 볼 수 있는 "Fence Rails" 문제는 백준 사이트의 영어 원본과 완벽히 일치한다.
      • 영어 원본 문제와 백준 한글 번역본의 차이점이 하나 있는데, 영어 원본 문제에는 없는 제한 사항인 "각각의 길이는 100,000을 넘지 않는 양의 정수이다." 라는 문장이 한글 번역본에 추가되어 있다. 이 깃허브에 있는 테스트케이스로는 배낭의 최대 제한이 100,000은 커녕 10,000을 넘는 입력도 들어오지 않는 것으로 보인다.
    • USACO Training Problems 모음집의 제일 뒤쪽에는 각 문제에 대한 힌트가 적혀 있다. 아래는 "Fence Trails"에 대한 힌트이다.
      • 이 문제는 고차원 다중 배낭 문제이므로, 모든 경우를 직접 검사해야 합니다. 어떤 상태에서 다음 상태로의 분기(out-degree)가 높기 때문에, 트리의 깊이를 제한하기 위해 Iterative Deepening을 적용한 DFS를 사용해야 합니다.
      • 하지만 일반적인 Iterative Deepening을 적용한 DFS는 너무 느릴 수 있으므로, 몇 가지 가지치기가 필수적입니다.

풀이 관련

  • 어떤 중국인의 블로그에서 해결 코드와 풀이 아이디어를 찾을 수 있었다. 정리하자면 다음과 같다. (원본 문제는 나무판자와 레일이지만 배낭과 물건으로 바꾸어 정리했다.)
    1. x개의 물건을 담을 수 있는지 확인할 때, 당연히 가장 길이가 짧은 x개의 물건을 우선적으로 담아보는 것이 유리합니다. 따라서 배낭과 물건을 길이 오름차순으로 각각 정렬해줍니다.
    2. 큰 물건은 배낭에 담기 까다롭습니다. 작은 물건을 담기 위해 큰 가방을 소비해버리면 나중에 큰 물건을 담을 수 없을 수도 있기 때문에 반드시 큰 물건부터 배낭에 담도록 시도해야 합니다. 극단적인 예시로 담아야 할 가장 무거운 물건이 가장 큰 배낭의 제한보다 크다면 이 탐색은 즉시 실패를 반환해야 합니다. 하지만 작은 물건부터 담게 되면 무수히 많은 헛된 탐색을 해야 합니다.
    3. 탐색 도중 i번째 배낭과 j번째 배낭의 여유 무게가 같다면 현재 담으려는 물건은 i번째에 담든 j번째에 담든 결과적으로 아무런 차이가 없습니다.
    4. 담을 i번째 물건과 j번째 물건의 무게가 같다면 (배낭 A에 i번째 물건을 담고 배낭 B에 j번째 물건을 담는 경우)와 (배낭 A에 j번째 물건을 담고 배낭 B에 i번째 물건을 담는 경우)는 완전히 동일한 상황입니다. 따라서 무게가 같은 물건들을 담을 때는, 물건을 담는 배낭의 번호가 감소하지 않도록 강제하여 동일한 조합의 중복 탐색을 피해야 합니다.
    5. 탐색 과정에서 어떤 배낭의 남은 여유 공간이 아직 배낭에 담지 않은 물건 중 최소 무게보다 작다면 이 여유 공간은 물건을 절대 담을 수 없는 버려지는 공간이 됩니다. 만약 이 (버려지는 공간의 합)이 (전체 배낭 제한의 합) - (현재 만들고자 하는 x개 물건의 합)보다 커진다면, 이 방식으로는 절대 목표를 달성할 수 없으므로 즉시 해당 탐색 분기를 종료합니다.
    6. 선택된 x개 물건 중 어떤 물건의 무게와 어떤 배낭의 무게 제한이 완벽히 일치한다면 그 물건은 무조건 그 배낭에 담는 것이 최적해입니다.
  • 나는 여기에 한 가지 가지치기를 더 추가했다. DLAS 휴리스틱에서 사용되는 "현재 최적해를 도출한 후 k번 이상 연산하여 더 이상 최적해를 갱신하지 못한 경우 종료한다"는 아이디어를 사용해, "현재 배낭에 x개의 물건을 담기 위해 탐색한 횟수가 10,000번이 넘어갈 경우 x개의 물건은 담지 못하는 것으로 판단"하는 것이다.
    • 이 가지치기를 추가하지 않은 경우 19%에서 TLE를 받는다.
    • 이 탐색 횟수를 500,000번으로 잡았을 때 236ms가 나왔고, 100,000번으로 잡았을 때는 188ms, 10,000번으로 잡았을 때 148ms, 7,000번으로 잡았을 때 140ms가 나왔다. 다만 5,000번으로 잡은 경우 26%에서 WA를 받게 된다.
  • 전체적인 흐름을 정리하면 다음과 같다. 결정 문제를 "현재 배낭에 x개의 물건을 담을 수 있는가?"를 잡고 이분 탐색으로 x의 최대값을 구하면 된다. 결정 문제는 위의 가지치기를 적용시킨 DFS로 확인해주면 된다.
  • 엄청 큰 데이터에 대한 테스트는 질문 게시판의 doju님이 추가하신 반례로 수행했다.
    • input, output
    • input :
50
1388 1398 1524 1370 1384 1294 1436 1254 1320 1340 1414 1176 1688 1258 1362 1248 1556 1395 1329 1408 1136 1486 1526 1246 1494 1376 1228 958 1306 1382 1666 1576 1328 1336 1082 1562 1358 1320 1654 1248 1312 1444 1438 1150 1502 1536 1316 1460 1622 1316
1023
28 90 10 26 74 32 78 24 50 108 20 104 58 78 114 18 86 64 116 120 98 14 50 38 42 34 72 92 114 12 64 68 62 128 46 90 82 36 114 96 102 48 72 44 36 78 62 96 128 48 40 30 32 54 90 110 72 98 28 52 32 44 16 64 50 94 40 44 60 72 68 40 32 28 110 126 112 64 78 12 54 82 110 76 56 78 104 90 42 22 102 62 70 38 26 18 50 52 100 38 40 78 88 78 80 78 12 92 64 100 112 100 46 96 58 18 106 42 122 36 84 104 102 80 36 100 42 44 16 52 30 100 102 114 98 94 122 48 24 34 38 12 34 72 98 72 56 16 56 60 114 10 22 124 60 26 92 24 52 116 48 68 68 120 98 22 80 60 26 30 20 98 14 114 80 60 92 24 14 28 28 48 24 108 24 40 74 10 28 122 30 78 108 22 104 18 64 120 32 66 38 116 50 32 114 84 122 112 88 102 18 122 58 24 32 60 30 58 18 106 16 48 52 80 56 16 18 114 16 66 40 34 96 12 46 84 18 16 32 22 14 70 24 102 52 82 118 80 96 20 128 88 18 48 50 50 76 72 14 122 128 112 40 18 98 118 16 128 114 122 80 36 114 84 84 46 92 96 78 116 34 30 64 118 10 28 122 28 118 108 76 34 122 90 22 70 66 120 36 86 10 24 24 110 52 58 66 78 74 12 80 36 28 22 120 110 96 44 62 12 126 114 92 72 12 120 60 54 14 118 80 34 42 24 54 28 10 80 24 120 64 60 66 40 58 50 90 82 96 30 50 58 66 100 82 106 112 48 60 124 50 20 118 70 34 128 108 106 108 40 48 120 32 46 102 98 28 124 28 68 62 124 102 68 78 72 48 24 24 24 70 58 64 126 90 102 56 106 24 44 76 66 60 96 12 26 114 62 22 108 24 76 60 14 126 100 104 68 86 72 38 24 64 66 126 72 52 62 128 10 82 12 52 78 14 30 104 46 76 68 66 52 120 102 72 76 94 96 76 78 78 124 44 32 40 26 48 38 44 76 126 108 62 96 44 100 70 116 114 98 66 48 84 76 52 92 36 50 118 56 76 58 92 42 50 32 116 10 48 50 56 22 110 96 124 32 60 10 82 66 104 44 40 34 74 110 118 62 112 126 18 90 76 120 72 62 52 64 88 16 72 94 80 48 12 118 128 48 110 56 90 110 116 52 72 126 82 56 74 92 16 94 104 120 74 102 64 124 44 90 112 104 14 116 88 56 108 34 64 60 38 26 68 108 102 80 48 68 116 50 22 56 30 22 22 48 102 26 82 102 104 68 26 110 28 78 28 62 82 122 92 42 48 10 38 64 22 94 74 104 20 18 90 124 68 76 50 16 68 84 114 72 14 38 26 128 18 56 126 118 118 100 64 124 40 50 104 38 92 70 64 66 48 68 86 28 64 54 120 38 16 112 100 22 100 44 126 16 58 56 116 40 54 124 48 78 106 80 106 96 42 66 76 66 52 76 106 116 20 22 98 104 108 22 94 82 98 60 24 32 74 122 16 76 122 120 20 66 50 26 42 110 116 54 30 118 20 24 24 44 36 66 116 80 90 84 68 104 52 36 114 48 20 78 28 10 70 78 86 128 34 82 14 114 18 86 12 34 40 122 126 106 12 74 124 88 76 28 98 94 20 26 64 14 126 50 32 20 94 68 58 116 34 92 58 36 116 78 28 28 48 44 118 50 104 96 100 118 94 94 58 126 108 32 96 42 70 56 104 96 36 128 76 42 72 24 96 12 118 78 64 56 68 92 80 106 18 116 32 114 68 80 26 12 10 38 10 102 10 10 72 98 20 30 24 46 96 106 92 28 54 88 78 22 94 36 114 122 124 110 104 68 12 58 90 80 94 86 110 34 70 74 38 120 78 42 104 34 118 64 48 100 98 16 60 16 120 128 94 32 52 88 40 112 56 50 30 24 10 84 52 32 82 86 116 24 60 12 100 96 118 14 54 124 102 88 32 18 92 94 44 124 30 70 112 68 58 80 46 48 46 104 70 56 64 70 114 72 88 128 66 44 110 34 92 98 96 40 12 50 110 90 64 124 78 112 40 124 88 82 128 60 98 96 78 120 38 92 110 96 78 128 58 26 10 108 26 42 18 22 94 18 58 122 28 92 70 20 78 34 18 96 34 28 106 30 78 110 30 46 108 22 12 80 128 54 32 26 26 76 28 18 80 82 12 104 80 46 104 70 36 12 116 42 74 40 44 104 68 128 26 14 18 48 24 116 28 74 18 94 14 120 122 78 104 84 120 42 24 54 64 46 36
output :
1022
  • jinsung님이 질문 게시판에 올리신 다른 테스트케이스이다. 이 테스트케이스가 채점 데이터에 추가된 것인지는 잘 모르겠다. 정답을 빠르고 정확하게 출력하는지 확인하는 용도로 사용하면 좋을 것 같다.
    • input :
50
1383 1393 1519 1365 1379 1289 1431 1249 1315 1335 1409 1171 1688 1253 1357 1243 1551 1390 1324 1403 1131 1481 1521 1241 1489 1371 1223 953 1301 1377 1661 1571 1323 1331 1077 1557 1353 1315 1649 1243 1307 1439 1433 1145 1497 1531 1311 1455 1617 1311
1023
128 90 10 26 74 32 78 24 50 108 20 104 58 78 114 18 86 64 116 120 98 14 50 38 42 34 72 92 114 121 64 68 62 128 46 110 82 36 114 96 102 48 72 44 36 78 62 96 128 48 40 30 32 54 90 110 72 98 28 52 32 44 16 64 50 94 40 44 60 72 68 40 32 28 110 126 112 64 78 12 54 82 110 76 56 78 104 90 42 22 102 62 70 38 26 18 50 52 100 38 40 78 88 78 80 78 12 92 64 100 112 100 46 96 58 18 106 42 122 36 84 104 102 80 36 100 42 44 16 52 30 100 102 114 98 94 122 48 24 34 38 12 34 72 98 72 56 16 56 60 114 10 22 124 60 26 92 24 52 116 48 68 68 120 98 22 80 60 26 30 20 98 14 114 80 60 92 24 14 28 28 48 24 108 24 40 74 10 28 122 30 78 108 22 104 18 64 120 32 66 38 116 50 32 114 84 122 112 88 102 18 122 58 24 32 60 30 58 18 106 16 48 52 80 56 16 18 114 16 66 40 34 96 12 46 84 18 16 32 22 14 70 24 102 52 82 118 80 96 20 128 88 18 48 50 50 76 72 14 122 128 112 40 18 98 118 16 128 114 122 80 36 114 84 84 46 92 96 78 116 34 30 64 118 10 28 122 28 118 108 76 34 122 90 22 70 66 120 36 86 10 24 24 110 52 58 66 78 74 12 80 36 28 22 120 110 96 44 62 12 126 114 92 72 12 120 60 54 14 118 80 34 42 24 54 28 10 80 24 120 64 60 66 40 58 50 90 82 96 30 50 58 66 100 82 106 112 48 60 124 50 20 118 70 34 128 108 106 108 40 48 120 32 46 102 98 28 124 28 68 62 124 102 68 78 72 48 24 24 24 70 58 64 126 90 102 56 106 24 44 76 66 60 96 12 26 114 62 22 108 24 76 60 14 126 100 104 68 86 72 38 24 64 66 126 72 52 62 128 10 82 12 52 78 14 30 104 46 76 68 66 52 120 102 72 76 94 96 76 78 78 124 44 32 40 26 48 38 44 76 126 108 62 96 44 100 70 116 114 98 66 48 84 76 52 92 36 50 118 56 76 58 92 42 50 32 116 10 48 50 56 22 110 96 124 32 60 10 82 66 104 44 40 34 74 110 118 62 112 126 18 90 76 120 72 62 52 64 88 16 72 94 80 48 12 118 128 48 110 56 90 110 116 52 72 126 82 56 74 92 16 94 104 120 74 102 64 124 44 90 112 104 14 116 88 56 108 34 64 60 38 26 68 108 102 80 48 68 116 50 22 56 30 22 22 48 102 26 82 102 104 68 26 110 28 78 28 62 82 122 92 42 48 10 38 64 22 94 74 104 20 18 90 124 68 76 50 16 68 84 114 72 14 38 26 128 18 56 126 118 118 100 64 124 40 50 104 38 92 70 64 66 48 68 86 28 64 54 120 38 16 112 100 22 100 44 126 16 58 56 116 40 54 124 48 78 106 80 106 96 42 66 76 66 52 76 106 116 20 22 98 104 108 22 94 82 98 60 24 32 74 122 16 76 122 120 20 66 50 26 42 110 116 54 30 118 20 24 24 44 36 66 116 80 90 84 68 104 52 36 114 48 20 78 28 10 70 78 86 128 34 82 14 114 18 86 12 34 40 122 126 106 12 74 124 88 76 28 98 94 20 26 64 14 126 50 32 20 94 68 58 116 34 92 58 36 116 78 28 28 48 44 118 50 104 96 100 118 94 94 58 126 108 32 96 42 70 56 104 96 36 128 76 42 72 24 96 12 118 78 64 56 68 92 80 106 18 116 32 114 68 80 26 12 10 38 10 102 10 10 72 98 20 30 24 46 96 106 92 28 54 88 78 22 94 36 114 122 124 110 104 68 12 58 90 80 94 86 110 34 70 74 38 120 78 42 104 34 118 64 48 100 98 16 60 16 120 128 94 32 52 88 40 112 56 50 30 24 10 84 52 32 82 86 116 24 60 12 100 96 118 14 54 124 102 88 32 18 92 94 44 124 30 70 112 68 58 80 46 48 46 104 70 56 64 70 114 72 88 128 66 44 110 34 92 98 96 40 12 50 110 90 64 124 78 112 40 124 88 82 128 60 98 96 78 120 38 92 110 96 78 128 58 26 10 108 26 42 18 22 94 18 58 122 28 92 70 20 78 34 18 96 34 28 106 30 78 110 30 46 108 22 12 80 128 54 32 26 26 76 28 18 80 82 12 104 80 46 104 70 36 12 116 42 74 40 44 104 68 128 26 14 18 48 24 116 28 74 18 94 14 120 122 78 104 84 120 42 24 54 64 46 36
output :
1018

profile
cl2380
이전 포스트

백준 3178 - 코코스 (Python)

0개의 댓글