[7주차_금요일] 수도배관공사

[KodaHye]

• 사이트 : 백준(BOJ)
• 문제: 수도배관공사
• 번호: 2073

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 7 ≤ D ≤ 100,000, 1 ≤ P ≤ 350 → D x P < 10^9이므로 O(N^2) 가능
• DP, Knapscak

💡 풀이 아이디어

• 길이를 만들었을 때 값 찾기 + 아이템이 정해져 있음 → Knapsack
• 특정 길이에서 값을 갱신할 때 파이프의 넓이가 작아질 수도 있다.
• 따라서 특정 길이를 만들 때, 최대 파이프 넓이를 구해줘야 함

int[] dp = new int[d + 1];
dp[0] = Integer.MAX_VALUE; // 최솟값을 찾기 위해 첫 시작은 최대로 초기화
// 중복 선택이 불가능한 0-1 Knapsack
for (int i = 0; i < p; i++) {
    for (int j = d; j >= length[i]; j--) {
        // j길이를 만들었을 때 가질 수 있는 파이프의 최대 넓이
        dp[j] = Math.max(dp[j], Math.min(dp[j - length[i]], width[i]));
    }
}
System.out.println(dp[d]);

문제가 신기했습니다

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ P ≤ 350 (파이프 개수)
• 7 ≤ D ≤ 100,000 (거리)
• 1 <= L, C <= 2^23
• O(N^2)가능

💡 풀이 아이디어

• 01냅색(중복X)
• 문제 조건
  • 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값
  • 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량 구하기
• dp[i] = k : 수도관 길이 j를 만들때 가능한 파이프의 최소용량 k
• 수도관 용량
  • 수도관을 이루는 파이프의 최소 값
  • 각 수도관을 만들어갈때 용량의 최소값을 선택해야함
  • Math.min(dp[j - len[i]], cost[i]) : 새로운 파이프를 추가할때 수도관을 이루는 전체 파이프에서 최소값 갱신
• 수도관 길이
  • 최종 수도관 길이 D를 만들기 위해선 최소 파이프들 중 큰 값을 선택해야함 -Math.max(dp[j], Math.min(dp[j - len[i]], cost[i])): 가능한 파이프 중 최대값을 골라, 최대 수도관 용량 구하기

  int[] dp = new int[D + 1];
  dp[0] = Integer.MAX_VALUE;
  for (int i = 1; i <= P; i++) {
      for (int j = D; j >= len[i]; j--) {
          dp[j] = Math.max(dp[j], Math.min(dp[j - len[i]], cost[i]));
      }
  }
  System.out.println(dp[D]);

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : D <=100_000, P<=350 O(D * P) -> O(N^2)

💡 풀이 아이디어

• 가능한 최대 수도관 용량을 구하는 프로그램
• D길이가 커서 배열 1차원으로 둠 -> dp[0] = Integer.MAX_VALUE;
• L, C를 입력 받고 최소 파이프들 중 큰 값을 선택

      for(int i=1; i<=P; i++){
          st = new StringTokenizer(br.readLine());
          int L = Integer.parseInt(st.nextToken());
          int C = Integer.parseInt(st.nextToken());
          for(int j = D; j>= L; j--){
              dp[j] = Math.max(dp[j], Math.min(C, dp[j-L]));
          }
      }

[KodaHye]

🤔 시간복잡도 고려사항

• 7 <= 거리 <= 100_000
• 1 <= 파이프의 개수 <= 350

거리 × 파이프의 개수 < 1억 (거의 1억에 가까움) 이내로 풀이해야 됨

💡 풀이 아이디어

• 1차원 dp 배열 사용
• dp[0] = Integer.MAX_VALUE로 초기화

for(int i = 1; i < P + 1; i++) {
    for(int j = D; j >= pipes[i].l; j--) {
        int min = Math.min(dp[j - pipes[i].l], pipes[i].c);
        dp[j] = Math.max(dp[j], min);
    }
}

[yeongleej]

🤔 시간복잡도 고려사항

• 수도관 길이: D ≤ 100,000
• 파이프 개수 : P ≤ 350
• L[i], C[i] ≤ 2^23

=> O(D * P) 가능

💡 풀이 아이디어

• 각 파이프는 1개씩 사용되야 함 => 중복 X
• 각 파이프는 나눌 수 없음 => 0-1 Knapsack
• dp[j] : 길이가 j일 때 최대 수도관 용량

  max(dp[j], i번째 파이프를 추가할 때 용량)

• 수도관 용량 : 길이 j를 이루는 파이프들의 용량 중 가장 작은 값
  • i번째 파이프 길이가 L[i]일 때,

    min( j-L[i]인 수도관 용량, i번째 용량)

• (최솟값을 찾기 위해) j == L[i] 즉, i번째 파이프 하나만 선택했을 때는 i번째의 용량인 C[i]로 초기화하기 위해 dp[0] = Integer.MAX_VALUE로 초기화

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dp > 0-1냅색 알고리즘(중복X)
• 시간복잡도: 7 ≤ D ≤ 100,000 1 ≤ P ≤ 350 냅색알고리즘으로 풀이 시 O(D*P) 10^6 으로 풀이가능

💡 풀이 아이디어

• 특정 거리(k)만큼 파이프를 설치하여 최대 용량(v) 구하기.

dp[j] = Math.max(dp[j], Math.min(dp[j - len[i]], cost[i]));

수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값 → 수도관의 용량 = 어떤 수도관을 만들었을 때 여러 파이프 구성 중에 용량이 가장 작은 값

• Math.min(dp[j - len[i]], cost[i])
  • dp[j - len[i]] 현재 파이프를 추가하기 전 이전 상태에 대한 용량
  • cost[i] 현재 파이프의 용량

완성된 파이프들 중 가장 큰 용량을 구해야 한다. → 만들어진 여러개의 수도관 중 최대 용량 구하기 (수도관은 최소 1개 이상 만들 수 있음)

• Math.max(dp[j], 최소 용량)