절망적인 줄
문제
해빈시의 공원에는 화장실이 두 개가 있다. 그런데 그 중 하나가 얼마전에 고장났다. 이제 남은 건 한 개 뿐이다….
문제는 해빈이는 당장 화장실이 가고 싶은데, 화장실 앞의 줄이 매우 길다는 것이다!
고통을 잊기 위해 해빈이는 절망적인 줄을 쳐다보며 아래와 같은 문제를 풀기 시작했다.
화장실 사용료는 50원이다. 줄에 서 있는 사람들 중 반은 50원 동전을 가지고 있고, 나머지 반은 100원 동전만 가지고 있다.
화장실을 개장할 때, 관리인은 거슬러 줄 동전을 가지고 있지 않다.
100원 동전만 가진 사람에게는 50원 동전을 거슬러 줘야 한다.
(이 경우, 50원 동전을 가진 사람이 먼저 등어가면서 지불한 동전을 거스름돈으로 사용한다)
사람들의 위치를 적절히 바꿔서 관리인의 거스름돈이 항상 모자라지 않게 하는 방법의 수를 구하라.
이때, 일부 사람들은 절대로 자리를 바꾸지 않는다. (뒤쪽, 앞쪽 모두 다)
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 길이가 n (1 ≤ n ≤ 1,000) 인 문자열 한 줄로 이루어져 있으며,
50원 동전을 가지고 있으면서 자리를 바꾸길 원치 않는 사람을 나타내는 ‘(‘와 100원 동전을 가지고 있으면서
자리를 바꾸길 원치 않는 사람을 나타내는 ‘)’, 자리를 바꿔도 되는 사람을 나타내는 ‘.’으로 이루어져 있다.
’(‘와 ‘)’의 개수는 각각 n/2개 이하이고, n은 항상 짝수이다.
출력
각 테스트 케이스에 대해 문제의 조건을 지키며 자리를 바꿀 수 있는 방법의 수를 출력하라.
단, 문제의 답이 매우 커질 수 있으므로 마지막 여섯자리만 출력한다.
1
2
3
4
5
6
7
8
9
10
11
예제 입력 1
....
.(..
)...
.....)......................
예제 출력 1
2
1
0
68484
풀이
DP 문제라고는 생각을 못해서 접근을 전혀 하지 않았다.
아이디어를 알고 나니 어떻게 해야 할지는 알겠다.
헷갈렸던 문제들을 이렇게 정리하다보니 DP에 확실히 약한 것 같다. 아이디어가 잘 안 떠올라.
dp[i][j] 배열을 만들어서 j는 수중의 50원 동전, i는 지나간 사람 명 수로 본다.
50원 동전의 개수가 총 개수의 절반이라는 조건도 있고, 반복문을 돌리면 값이 나온다.
2개의 변하는 값? 저장하면서 풀어나가야 할 때 dp 아이디어를 제일 먼저 찾아보는 연습을 하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
int n, m, t;
string s;
while(getline(cin, s)){
int len = s.size();
int h = len/2;
vector<vector<long long>> v(len, vector<long long>(h+1,0));
if(s[0]==')')v[0][0]=0;
else{
v[0][1] = 1;
}
for(int i=1;i<len;i++){
if(s[i]==')'){
for(int j=0;j<h;j++){
v[i][j] += v[i-1][j+1]%1000000;
}
}
else if(s[i]=='('){
for(int j=1;j<=h;j++){
v[i][j] += v[i-1][j-1]%1000000;
}
}
else{
for(int j=0;j<h;j++){
v[i][j] += v[i-1][j+1]%1000000;
}
for(int j=1;j<=h;j++){
v[i][j] += v[i-1][j-1]%1000000;
}
}
}
cout << v[len-1][0]%1000000 << '\n';
}
return 0;
}