Algorithm, boj, 출근기록(14238)
다른분 풀이
-
메모라이즈를 통해 Bool 형태의 배열을 만들어놓고 가능하면 True를 아니면 False를 반환한다
-
DP[사용한 A의 개수][사용한 B의 개수][사용한 C의 개수][마지막에서 2번째로 사용한 문자][마지막으로 사용한 문자] 형태의 배열을 사용한다
#include <iostream>
#include <string>
using namespace std;
int have_alpha[3]; //입력받은 alphabet 개수 체크
string s;
bool dp[51][51][51][3][3] = { false, };
char ans[51];
bool start(int a, int b, int c, int back1,int back2) {
if (a==have_alpha[0] && b == have_alpha[1] && c == have_alpha[2]) {
return true;
}
if (dp[a][b][c][back1][back2]) return false;
dp[a][b][c][back1][back2] = true;
if (a+1<=have_alpha[0]) { //a 사용 가능
ans[a + b + c] = 'A';
if (start(a + 1, b, c, back2, 0))
return true;
}
if (b + 1 <= have_alpha[1]) {
ans[a + b + c] = 'B';
if (back2 != 1) { //b 사용 가능
if (start(a, b + 1, c, back2, 1))
return true;
}
}
if (c + 1 <= have_alpha[2]) {
ans[a + b + c] = 'C';
if (back1 != 2 && back2 != 2) { //c 사용 가능
if (start(a, b, c + 1, back2, 2))
return true;
}
}
return false;
}
int main() {
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == 'A') have_alpha[0]++;
else if (s[i] == 'B') have_alpha[1]++;
else have_alpha[2]++;
}
if (start(0, 0, 0, -1, -1))
for (int i = 0; i < s.size(); i++)
cout << ans[i];
else cout << -1;
system("pause");
return 0;
}
나의 코드
- 현재자리에는 a,b,c 세개가 규칙에 위배되지 않을경우 각각 올수있다.
- dp[x][c][b][a] : x까지의 a,b,c를 사용해서 만들수있는지 확인한다.
내 풀이의 개선점
- DP[사용한 A의 개수][사용한 B의 개수][사용한 C의 개수][마지막에서 2번째로 사용한 문자][마지막으로 사용한 문자] 내풀이 보다는 이걸로 바꾸는게 좋을것같다.
- 내 풀이의 x는 a+b+c 개수를 각각 더하면 쉽게 알수있고, 중요한 정보가 아니다.
- 여기서 중요한건 마지막으로 사용, 마지막 전에 사용한 문자가 중요하다.
package org.baekjoon;
import java.util.Scanner;
public class test14238 {
static int length;
static boolean[][][][] dp;
static char S[];
static final int NOT_EXIST = -1;
static int A = 0, B = 0, C = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
length = str.length();
// dp[x][c][b][a] : x까지의 a,b,c를 사용해서 만들수있는지 확인한다.
dp = new boolean[length][length][length][length];
S = new char[length];
for (int i = 0; i < length; i++) {
switch (str.charAt(i)) {
case 'A':
A++;
break;
case 'B':
B++;
break;
case 'C':
C++;
break;
}
}
if (solve(0, 0, 0, 0)) {
System.out.println(new String(S));
} else {
System.out.println(NOT_EXIST);
}
}
private static boolean solve(int x, int c, int b, int a) {
//System.out.println("x=" + x + " c=" + c + " b=" + b + " a=" + a + " string=" + new String(S));
if (x == length) {
return true;
}
// x자리 까지 a,b,c 를 사용해서 가능한지 확인했었기 때문에 또 확인 하지 않는다.
if (dp[x][c][b][a] == true)
return false;
// x위치에서 A를 a개 B를 b개 C를c개 사용해서 문자열 만들수있는지 확인할것이므로 true
dp[x][c][b][a] = true;
// X위치에 C,B,A가 들어갈수있는지 확인한다.
// 남아있는 C개수가있는지 확인 후 사용.
if (C > c) {
// 이전, 이이전에 사용했는지 확인후 아니라면 시도해본다.
if ((x >= 2 && (S[x - 1] != 'C' && S[x - 2] != 'C')) ||
(x == 1 && S[x - 1] != 'C') || x == 0) {
S[x] = 'C';
if (solve(x + 1, c + 1, b, a))
return true;
}
else // 규칙에 의해 검사 못했으므로 다시 false해준다.
dp[x][c][b][a] = false;
}
// 남아있는 B개수가있는지 확인 후 사용.
if (B > b) {
// 이전에 사용했는지 확인하고 아니라면 시도한다.
if ((x >= 1 && S[x - 1] != 'B') || x == 0) {
S[x] = 'B';
if (solve(x + 1, c, b + 1, a))
return true;
}else
dp[x][c][b][a] = false;
}
// 남아있는 A개수가있는지 확인 후 사용.
if (A > a) {
// 아무때나 시도 가능.
S[x] = 'A';
if (solve(x + 1, c, b, a + 1))
return true;
}
return false;
}
}