[7주차_금요일] 안녕

[KodaHye]

• 사이트 : 백준(BOJ)
• 문제: 안녕
• 번호: 1535

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

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• N ≤ 20, 체력 ≤ 100 → Knapsack 사용해도 무리가 없음

💡 풀이 아이디어

• 0-1 Knapsack의 기본 문제
• 체력이 0과 음수가 되면 안되기 때문에 최대 체력을 99로 설정 → 어떻게든 1이 남음

  int[] dp = new int[100];
  // 중복 선택이 불가능한 0-1 Knapsack
  for (int i = 0; i < n; i++) {
  for (int j = 99; j >= cost[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - cost[i]] + get[i]);
  }
  }
  System.out.println(dp[99]);

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : N=20, 체력 = 100 -> O(N^2)가능

💡 풀이 아이디어

• 제한된 체력으로 최적의 기쁨을 얻는 문제 -> 배낭 -> 인사O or 인사 X -> 0-1 배낭 문제
• 배낭 용량이 크지 않기에 2차원 배열 사용
• 체력이 0이나 음수가 되면 안되기에 K=99 -int[] weight : 체력, int[] value : 기쁨

      int[][] dp = new int[N+1][K+1];
      for(int i=1; i<=N; i++){
          for(int j=1; j<=K; j++){
              if(weight[i]<= j) {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - (weight[i])] + value[i]);
              }
              else dp[i][j] = dp[i-1][j]; // 인사하지 않는 경우
          }
      }

[baexxbin]

🤔 시간복잡도 고려사항

• N ≤ 20
• 체력 ≤ 100
• O(N^2) 가능

💡 풀이 아이디어

• 01배낭 문제(중복 불가)
• 해당 문제에선, 체력이 0이되면 안되기에 dp[health]가 아닌, dp[health-1]값 사용

  int[] dp = new int[health + 1];
  for (int i = 1; i <= N; i++) {
      for (int j = health; j >= hp[i]; j--) {
          dp[j] = Math.max(dp[j], dp[j - hp[i]] + happy[i]);
      }
  }

  System.out.println(dp[health-1]);

[yeongleej]

🤔 시간복잡도 고려사항

• 사람 수: N≤ 20
• 체력 ≤ 100

=> 완전탐색도 가능

💡 풀이 아이디어

• 각 사람에게 최대 1번만 말할 수 있으므로 0-1 Knapsack
• dp[j] : 체력이 j가 될 때, 최대 기쁨가치
  • 1차원 배열이므로 최대 체력부터 탐색
• 체력이 0이되면 죽기 때문에 😢 -j>h[i]: j가 체력보다 클 때만 인사하기

  for(int i=1; i<N+1; i++) {
      for(int j=MAX_HP; j>h[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j-h[i]]+v[i]);
      }
  }

[KodaHye]

🤔 시간복잡도 고려사항

• 사람의 수 <= 20
• 세준이의 체력 100

1) 완탐: 사람을 선택하는 모든 경우를 고려했을 때, 2^20 으로 문제 풀이 가능 2) Knapsack: 사람의 수 × 100으로 문제 풀이 가능

💡 풀이 아이디어

• 1차원 dp 배열을 통해 문제 풀이
• int[] dp = new int[101]
  • dp[i]: 체력을 i만큼 사용했을 때, 얻을 수 있는 최대 기쁨
• int[] W: 각각의 사람에게 인사를 할 때, 잃는 체력 (무게)
• int[] V: 인사를 할 때 얻는 기쁨 (가치)

for(int i = 1; i < N + 1; i++) {
    for(int k = 100; k > W[i]; k--) {
        dp[k] = Math.max(dp[k], dp[k - W[i]] + V[i]);
    }
}

[yeahdy]

🤔 시간복잡도 고려사항

알고리즘: dp > 0-1냅색 알고리즘(중복X)

• 시간복잡도: 사람의 수 N(≤ 20), 0<= 체력,기쁨 <= 100 0-1냅색 알고리즘으로 풀이 시 N*100

💡 풀이 아이디어

• 주어진 체력(100) 이내에 특정 체력만큼 소진했을 때 구할 수 있는 최대 기쁨 구하기
• 특정 체력(n)일 때 현재 체력(k)을 고려해서 최대기쁨(v)을 찾아야함
  • 0-1 배낭문제와 같음

    final int MAX_STAMINA = 100;
    int[] dp = new int[MAX_STAMINA+1];   //dp[체력]= 최대 기쁨
    for(int i = 1; i < N+1; i++){
      for(int stamina=MAX_STAMINA; stamina > 0; stamina--) {   
          int total = stamina-exhaustion[i]; 
          if (total > 0) {
              dp[stamina] = Math.max(dp[stamina], dp[total] + happy[i]);    
          }
      }
    }

으아!!!!!!!!!!!!!!!!!!!!!나는 정말 멍청이에요!!!!!!!!!!!!!!!!! 오늘 냅색 리뷰했는데 왜 바로 응용을 못하는건지🤦‍♀️💦😭 dp[?] = 최대기쁨 얻고자하는 값을 얻기 위해 어떤 상태가 되어야하는지 기준 잡는게 어렵네요..