[5주차_수요일] 사탕가게

[yeongleej]

• 사이트 : 백준(BOJ)
• 문제: 사탕가게
• 번호: 4781

[icegosimperson]

🤔 시간복잡도 고려사항 n=5000(사탕 종류) m=100.00(입력 예산) 100 (정수 변환) 5000 10,000 = 50,000,000 -> 완전 탐색 불가 -> `O(nm)`

💡 풀이 아이디어

• 구매한 사탕 칼로리가 더 높은 사람이 이기는 문제 -> 그리디?

• 사탕을 분할할 수 없음 -> 그리디X -> DP

• dp 점화식

  for(int j = price; j <= m; j++) {
   dp[j] = Math.max(dp[j], dp[j - price] + calories);
  }

int m = (int) (temp * 100 + 0.5); // 변환하는 이유 : `rounding error`

배낭 문제 rounding error 해야하는 이유 : https://www.acmicpc.net/board/view/82054

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00 → n x (m x 100) = 5 * 10^7이므로 O(nm) 가능

💡 풀이 아이디어

• 쪼갤 수 없는을 보자마자 0-1 KnapSack
  • 가지고 있는 돈에서 최대 칼로리를 구해야 하는 문제기 때문에 확신
• 0.01 ≤ m ≤ 100.00의 소수점으로 인해 인덱스 계산이 어려움이 있으므로 정수화를 한 후에 진행

  int m = (int) Math.round(Double.parseDouble(st.nextToken()) * 100);

  • 정수화를 할 때, 부동소수점(floating-point) 수의 정확도의 문제 때문에 값을 제대로 저장하지 못한다고 하네요. 예를 들어 0.01을 정확히 저장하지 못하고 0.00999999...와 같은 값으로 저장될 수 있음

    부동소수점 값을 정수로 변환하는 과정에서 오차가 발생할 가능성이 있으므로, 이를 방지하기 위해 Math.round를 사용해 반올림 처리하는 것이 좋습니다. -chatGPT-

[yeongleej]

🤔 시간복잡도 고려사항

• 사탕 종류 수: 1 ≤ n ≤ 5,000
• 가격 범위 : 0.01 ≤ m ≤ 100.00 => 정수화: 약 10,000
• 완전탐색은 불가
• O(n) or O(m) 으로 생각해보기

💡 풀이 아이디어

• 실수인 가격을 정수화하기

  1. 단순히, 실수*100 (X)
     • 예를 들어, 8.00에 100을 곱하면 800이 될 것이라고 생각되지만, 실제로는 8.00 == 7.9999998… 을 의미하기 때문에 오류가 발생함
     • ⇒ 이는 10진법 수를 2진법으로 담는 과정에서 오차가 발생하기 때문이다.
     • 예) 5/3을 소수10번쨰 자리의 실수로 표현하면 1.6666666667로 표현되는데 사실은 이보다 더 소수점이 있기 때문에 정확하지 않음
  2. *오차값 더하기 : 실수100 + 0.5 (O)**
     • 정수로 변환해서 사용할 때는 일정 근사값까지는 같은 수로 처주는 것!
     • 예) 99.5≤100←100.5는 모두 정수 100으로 처주는 것
     • 즉, 반올림될때는 1이 증가하므로 절반만 0.5 증가시켜 오차값을 줄여줌
     • int m = (int)((실수)*100 + 0.5)

• dp 활용

  • dp[i] = 가격이 i일 때 살 수 있는 최대 칼로리
  • 점화식: dp[i] = max(dp[i], dp[i-p])

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 사탕 종류의 수 <= 5,000
• 1 <= 돈의 양 <= 100.00
• 완전 탐색이 아닌 다른 방법으로 풀어야 됨
  • 돈의 양에 따라 가능한 사탕 종류의 수를 구한다면 100 × 5,000 × 5,000 경우 이상이 됨
• 냅색 알고리즘을 사용하면 O(사탕 종류의 수)에 가능

💡 풀이 아이디어

• Candy: 사탕의 칼로리, 가격을 저장하는 객체
• dp[i][j]: i번째 사탕까지 고려하고, j원까지 쓸 수 있을 때, 살 수 있는 최대 칼로리

• 냅색 알고리즘

  for(int i = 1; i < dp.length; i++) {
      for(int j = 0; j < dp[0].length; j++) {
          if(j >= candys[i].p) {
              dp[i][j] = Math.max(candys[i].c + dp[i][j - candys[i].p], dp[i - 1][j]);
          } else {
              dp[i][j] = dp[i - 1][j];
          }
      }
  }

가격을 형변환하고 round하는 부분에서 잘 이해가 되지 않았는데, 지영님 댓글 보고 이해했습니다!!!!

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 5,000
• 0.01 ≤ m ≤ 100.00 (*100)
• 10^7
• 완전배낭문제로 풀 경우, O(N*M) (N:사탕 수, M: 최대 돈)

💡 풀이 아이디어

• 처음엔 01배낭 문제를 떠올렸으나, 사탕을 원하는 만큼 구매할 수 있기에 완전 배낭 문제

  • 01배낭 문제 : 아이템 0 or 1개 선택
  • 완전 배낭 문제 : 아이템 여러번 선택 가능

• dp 점화식

  • dp[i] = k : i원으로 얻을 수 있는 최대 칼로리 k
  • dp[j] = Math.max(dp[j], dp[j - price[i]] + cal[i]);

• 점화식 차이

  • 01배낭 문제
    • 가격 for문 거꾸로 탐색
    • 아이템을 하나만 선택해야하기에 dp[i] 업데이트 시 현재 아이템은 포함하지 않은 이전 상태를 참조해야 함
  • 완전 배낭 문제
    • 가격 for문 순차 탐색
    • 아이템 여러번 선택 가능하기에 동일한 아이템 반복 고려
    • j - price[i] 상태에서 같은 i번째 사탕 다시 고려 가능 (j - price[i]는 이미 i를 포함한 상태일 수 있음)

• 가격 정수화 주의

01배낭과 완전 배낭에 대한 학습을 더 해봐야할 것 같다! 다들 이슈에 잘 정리해주신 덕분에 가격 형변환 잘 이해하고갑니다!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP
• 시간복잡도: 사탕수 1 ≤ n ≤ 5,000 , 돈 100 ≤ m ≤ 10000 (소수점제거)
  • Knapsack 알고리즘: O(n * m) = O(5000 * 10000) = O(50,000,000) = 10^7
  • 사탕의 갯수-가격 조합을 고려하지 않아도 되기 때문에 dp 1차원 배열로 풀이 가능

💡 풀이 아이디어

• 그리디 방식이 아닌 DP 방식인 이유?
  • 최적의 해를 구하는 문제라서 그리디 방식을 떠올렸는데, 그리디 방식의 경우 현재 상황에서의 최적의 해를 구하는 것이기 때문에 전체 최적해를 보장하지 않는다 문제는 전체에서 사탕을 골랐는 때 최적의 해를 구해야 하기 때문에 DP 를 사용해야함
• DP 대표문제인 배낭문제와 유사하지만 다름
  • 각 사탕의 갯수와 가격의 조합을 구하지 않아도, 가격의 조합으로 최적의 칼로리만 구해도 됨
  • 동일한 종류의 사탕을 여러번 담을 수 있음