2차원 토마토 문제는 해본 적이 있다. 3차원 토마토 문제를 처음 겪어보았다.

• 2차원 토마토 문제 링크

우선, 토마토의 좌표를 나타내는 struct tomato를 선언했다.

  struct tomato {
      int x;
      int y;
      int z;
      tomato(int a, int b, int c) {
          x = a;  y = b;  z = c;
      }
  };

여섯 방향을 나타내는 dx[], dy[], dz[]를 선언했다.

  int dx[] = { 0, 1, 0, 0, -1, 0 };
  int dy[] = { 0, 0, 1, 0, 0, -1 };
  int dz[] = { 1, 0, 0, -1, 0, 0 };

토마토 정보를 m[101][101][101]에 받는다.

  // 익은 토마토일 경우, 익은 토마토를 기준으로 6 방향으로 나눠 안익은 토마토를 익혀가기 위해서 q에 추가한다.
  if (m[i][j][k] == 1)        q.push(make_pair(tomato(i, j, k), 0));
  // 비어있는 경우, emptyCnt++
  else if (m[i][j][k] == -1)  emptyCnt++;
  // 익지 않은 경우, rareCnt++
  else if (m[i][j][k] == 0)   rareCnt++;

토마토 상자 내에 있는 모든 토마토가 익어있는 경우를 처리한다.

  if (q.size() + emptyCnt == _x * _y * _z) {
      cout << 0;
      exit(0);
  }

BFS를 실시한다.

  while (!q.empty()) {
      int x = q.front().first.x;
      int y = q.front().first.y;
      int z = q.front().first.z;
      int day = q.front().second;
      q.pop();

      // day에서 제일 큰 값이 전체 토마토가 다 익는 날짜가 된다.
      answer = max(answer, day);

      for (int i = 0; i < 6; i++) {
          int xx = x + dx[i];
          int yy = y + dy[i];
          int zz = z + dz[i];

          if (isRare(xx, yy, zz)) {
              // 이제는 익었으므로 하나 줄여준다.
              rareCnt--;
              // 익었으므로 1로 표기
              m[xx][yy][zz] = 1;
              // 익은 토마토를 기준으로 BFS
              q.push(make_pair(tomato(xx, yy, zz), day + 1));
          }
      }
  }

• 내가 탐색하려는 index가 tar2일 때
• 최단 거리를 저장하는 answer와 cnt를 비교해서 더 작은 값으로 answer를 업데이트한다.

  // 사람 수 만큼 탐색
  for (int i = 1; i <= n; i++) {
      // 아직 탐색되지 않은 사람이고, 연결이 되어 있다면 dfs할 수 있다.
      if (visit[i] == 0 && m[index][i] == 1) {
          visit[i] = 1;
          dfs(i, cnt + 1);
          visit[i] = 0;
      }
  }

• 처음에 총 숫자의 갯수를 주고, 맨 마지막으로 주는 숫자는 플러스와 마이너스를 한 결과값, 나머지 중간에 있는 숫자는 피연산자들이다.

• i번째 피연산자를 플러스 또는 마이너스로 계산했을 때, 결과 j가 나오는 경우의 수를 저장한다.

• 첫 피연산자가 k라고 하면, 뺄수는 없으므로 dp[1][k] = 1이 된다.
• 연산의 초깃값이 k가 되고, k가 될 수 있는 경우의 수가 하나밖에 존재하지 않는다.

• dp[i - 1]를 순회하면서 피연산자 num를 더하거나 뺄 수 있는 후보를 찾는다. 후보를 찾았고, 그 후보에서 num을 더하거나 뺐을 때 0 이상 20 이하라면, dp[i][j + num] += dp[i - 1][j]; 혹은 dp[i][j - num] += dp[i - 1][j];를 한다.

  for (int i = 2; i <= n - 1; i++) {
    cin >> num;
    // dp[i - 1]에서 num을 더하거나 뺄 수 있는 후보 찾기
    for (int j = 0; j <= 20; j++) {
        // 후보를 찾았다.
        if (dp[i - 1][j] > 0) {
            // j에서 (후보의 연산 결과 값에서) num을 더하거나 뺐을 때 0이상 20이하라면 그 경우의 수를 더해준다.
            if (j + num <= 20)    dp[i][j + num] += dp[i - 1][j];
            if (j - num >= 0)     dp[i][j - num] += dp[i - 1][j];
        }
    }
  }

dp[i][j]

• i번째 음악 볼륨 리스트에서 볼륨을 오르내릴 때, j 크기의 볼륨을 가질 수 있는가.
• 가질 수 있다면 true, 가질 수 없다면 false.

dp[i][j]의 초깃값

• 아직 아무 음악을 탐색하지 않았으므로, 0번째 음악 리스트에는 초깃값 S 크기의 볼륨을 가질 수 있다.
• 즉, dp[0][s] = true;

dp[i][j] 탐색

• i번째 음악 볼륨 리스트에서 볼륨을 오르내릴 때, dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다. 후보를 찾고, i번째 음악 볼륨을 오르내려서 범위 내에 있다면, dp[i][오르내린 볼륨 결과]를 true로 만들어준다.

  // 음악을 1번 음악부터 n번 음악까지 탐색한다.
  for (int i = 1; i <= n; i++) {
    // i번째 음악 볼륨을 입력 받는다.
    cin >> v;
  
    // j-for문 : dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다.
    for (int j = 0; j <= m; j++) {
        // 볼륨을 오르내릴 후보를 찾았다
        if (dp[i - 1][j]) {
            if (j + v <= m) dp[i][j + v] = true;
            if (j - v >= 0) dp[i][j - v] = true;
        }
    }
  }

• i원이 되게 하는 최소 동전의 갯수를 저장한다.

  for (int j = coin; j <= k; j++) {
      dp[j] = min(dp[j], dp[j - coin] + 1);
  }

• 00과 1을 조합해서 i의 길이를 만들었을 때, 몇 개의 숫자를 만들 수 있는지 저장
• 이전 값에서 00을 붙여서 길이가 i인 숫자를 만들 수 있는 경우 : dp[i - 2]
• 이전 값에서 1을 붙여서 길이가 i인 숫자를 만들 수 있는 경우 : dp[i - 1]
• ∴ dp[i] = dp[i - 2] + dp[i - 1]

• i를 제곱수의 합으로 나타내었을 때 가질 수 있는 항의 최솟값을 저장한다.

  if (i == cnt * cnt) {
      dp[i] = 1;
      cnt++;
  }

• 18 = 16 + 1 + 1 = 9 + 9 인 경우도 있으므로, j-for문을 돌렸어야 했다.

    dp[i] = 2147000000;
    for (int j = 1; j <= cnt - 1; j++) {
        dp[i] = min(dp[i], 1 + dp[i - j * j]);
    }

• 자세한 정보

• 현재 배낭의 무게가 i일 때의 최대 가치를 저장

  for(int j = k; j >= w; j--){
      dp[j] = max(dp[j], dp[j - w] + v);
  }

• k는 가방의 제한 무게, w는 현재 검사하려는 물건의 무게, v는 현재 검사하려는 물건의 가치
• j-for문
  • j를 k부터 w까지 돌린다. j가 w보다 작은 값을 도는 것은 의미가 없다. 현재 검사하려는 물건의 무게가 w이므로, w 미만의 가방 무게에는 검사하려는 물건이 들어갈 수 없다.
  • dp[j]와 dp[j - w] + v 중 큰 값으로 dp[j]를 업데이트 한다.