ABC (BOJ 12969)

문제

이미지 클릭

문제 설명

• 문자열 s는 'A', 'B', "C'로 이루어져 있고 크기순서는 A <B <C순서이다.
• 0보다 크고 N보다 작은 i, j( i <j )가 있다고 할 때 s [i]<s [j]를 만족하는 개수가 총 K개가 되어야 한다.
• 단 여러 개가 존재할 경우에는 아무거나 출력해도 되고 A, B, C가 모두 포함될 필요는 없다.

문제 해설

• 동적 계획법: A의 개수, B의 개수, C의 개수, 모든 알파벳의 개수로 나누어서 재귀함수를 통해서 문자열을 만들어 나간다.

최종 코드

#include <iostream>
using namespace std;
int n, k;
int dp[31][31][31][504];
bool f(int x, int y, int z, int sum, string s) {
  if (x + y + z == n) { #알파벳의 총 개수가 n일떼
    if (sum == k) { 
      cout << s;
      return 1;
    }
    return 0;
  }
  if (dp[x][y][z][sum] != -1)  return 0;
  dp[x][y][z][sum] = 0;
  if (f(x + 1, y, z, sum, s + 'A')) return 1;
  if (f(x, y + 1, z, sum + x, s + 'B')) return 1;
  if (f(x, y, z + 1, sum + x + y, s + 'C')) return 1;
  return 0;
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i <= n; i++) { #-1로 dp 배열 초기화하기
    for (int j = 0; j <= n; j++) {
      for (int l = 0; l <= n; l++) {
        for (int m = 0; m <= 503; m++) {
          dp[i][j][l][m] = -1;
        }
      }
    }
  }
  if (!f(0, 0, 0, 0, "")) cout << -1;
}

• x: A의 개수
• y: B의 개수
• z: C의 개수
• sum: s [i]<s [j] ( 0 ≤ i < j < N )인 쌍들의 개수를 저장

if (f(x + 1, y, z, sum, s + 'A')) return 1;
  if (f(x, y + 1, z, sum + x, s + 'B')) return 1;
  if (f(x, y, z + 1, sum + x + y, s + 'C')) return 1;

1.  만약 A가 들어오게 된다면 A보다 큰 알파벳은 없기 때문에 sum을 그대로 보낸다.
2. 만약 B가 들어오게 된다면 B보다 작은 알파벳은 A이기 때문에 A의 개수 x를 sum에 더해준다.
3. 만약 C가 들어오게 된다면 C보다 작은 나머지 알파벳의 개수를 sum에 더해준다.

if (x + y + z == n) {
    if (sum == k) {
      cout << s;
      return 1;
    }
    return 0;
  }

• x+y+z, 즉 모든 알파벳의 개수가 n이 되고 sum이 k와 같다면 알파벳 문자열을 출력해 준다.

이미지 클릭