https://www.acmicpc.net/problem/1248
영어를 보니 현기증이 난다.
내용 자체는 생각보다 간단하다
해당 조건을 만족하는 수열을 찾아라!
1.n입력
2.부호입력
3.해당 부호에 맞는 수열 입력
해당 부호는
예를들어 수열이 3 -6 2 7일 경우
앞에서부터 하나씩 더한 값의 부호를 정하는 것이다.
ex)
3 = 3 +
3 - 6 = -3 -
3-6+2 = -1 -
3-6+2+7 = 6 +
즉 +--+ 이렇게나오고
그 다음은
맨 앞 수를 제외한 나머지도 똑같이 진행
-6 =-6 -
-6 +2 = -4 -
-6+2+7 = 3 +
- - +
...
이렇게 진행해 나가는 것인데
이것을 처음 입력단에 쓴 후 적절한 수열 아무거나 출력하라는 뜻이다.
예를들어 4 +--+--++++ 이렇게 되어있다면
앞서 말한 수열 3 -6 2 7 이 나오는 것
그렇다면 진행을 어떻게 해야될까?
먼저 수열 여러개를 택한 브루트 포스인걸 알겠으나
모든 방법을 고려하면 아마 시간초과가 뜰 것이다.
왜냐면 10CN번을 다돌리면 진짜 많거든...
먼저 시간초과가 뜬 나의 코드를 보여주겠따
---
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
bool visited[20];
int n;
char arr[10][10];
vector<int> v;
char s[10][10];
void task(int depth);
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
cin >> s[i][j];
}
task(0);
}
void task(int depth)
{
if (depth == n)
{
for (int i = 0; i < n; i++)
{
int temp_sum = 0;
for (int j = i; j < n; j++)
{
temp_sum += v[j];
if (s[i][j] == '+' && temp_sum <= 0)
return;
if (s[i][j] == '-' && temp_sum >= 0)
return;
if (s[i][j] == '0' && temp_sum != 0)
return;
}
}
for (int i = 0; i < n; i++)
cout << v[i] << " ";
cout << "\n";
exit(0);
}
for (int i = -10; i <= 10; i++)
{
v.push_back(i);
task(depth + 1);
v.pop_back();
}
}
해당 방법의 경우 중복을 피하라는 말은 없었다.
그래서 이제 그냥 내부에서 모든 수열을 더해주는 방식만 생각하면 된다.
for (int i = 0; i < n; i++)
{
int temp_sum = 0;
for (int j = i; j < n; j++)
{
temp_sum += v[j];
if (s[i][j] == '+' && temp_sum <= 0)
return;
if (s[i][j] == '-' && temp_sum >= 0)
return;
if (s[i][j] == '0' && temp_sum != 0)
return;
}
}
depth==n일때, 해당 방벙으로 진행하게되면
0, 0+1,0+1+2. 방법으로 계속 더해나갈 수 있다.
처음에 나는 저 s[i][j]와 +를 비교하려면 2가지 반복문을 모두 지난 후 더해야 된다 생각해서 오래걸렸다.
하지만 이렇게 앞에서부터 진행하면, 첫번째원소만을 더한값 , 첫번째원소 + 두번째원소.. 이렇게 차례차례 지나가며 i가 2로가면 다시 j=1부터 더해지는 방식을 깨달았다.
그래서결과는
오우 노우
대체 문제가 뭐야
앞서말한 시간초과의 문제의 위험성이였다.
사실 이 식은 depth==n이될때가지, 정말 수많은 가짓수를 거치며 ( 20개의 수 중에서 n개의 수열을 고름 )
최대 20C10 가지의 수를 찾아볼 수 있기 때문에
최악의 경우 백만가지 이상의 경우의 수를 돌 수 있다.
그렇다면 ?
how do i do?
저 중간에 보이는 조건문을 따로 빼주어, 수열을 정할 때, 조건에 맞지 않다면 바로 return해주는 것이다.
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
bool visited[20];
int n;
char arr[10][10];
vector<int> v;
char s[10][10];
void task(int depth);
bool isValid(int depth)
{
int sum = 0;
for (int i = depth; i >= 0; i--)
{
sum += v[i];
if (s[i][depth] == '+' && sum <= 0)
return false;
if (s[i][depth] == '-' && sum >= 0)
return false;
if (s[i][depth] == '0' && sum != 0)
return false;
}
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
cin >> s[i][j];
}
task(0);
}
void task(int depth)
{
if (depth == n)
{
for (int i = 0; i < n; i++)
cout << v[i] << " ";
cout << "\n";
exit(0);
}
for (int i = -10; i <= 10; i++)
{
v.push_back(i);
if (isValid(depth))
task(depth + 1);
v.pop_back();
}
}
이렇게 모든 수열을 구하는 백트래킹 과정에서, isValid인지 미리 구하는 것을 하면, 적절하지 않은 답들은 사전에 처리되어 무사히 통과할 수 있다.
짜잔