1239번

1239번 - 차트

permutation 함수를 사용해도 되지만, 그냥 재귀함수를 통해서 모든 경우의 수를 구했다.

N제한이 8이기 때문에, 충분히 구할 수 있는 경우의 수였다.

그리고 주어진 순서를 가지고 50의 값을 만들 수 있는 경우를 모두 확인한다.

이때 처음에 나는 while 문을 쓰지 않고 for문을 썼는데, 이럴 경우에 값을 더하다가 n에 막혀 더 못 더하는 경우가 발생했다.

밑에 원에서 왼쪽까지 구해야 하는데 , 오른쪽 까지만 구해서 답을 냈다.

이 오류를 못 찾아서 계속 헤맸다.. 결국 while 문을 써서 문제를 해결했다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int n, ans = 0;
vector<bool> used;
vector<int> v;
vector<int> op;
void go(int k)
{
    if (k == n)
    {
        int cnt = 0;
 
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            int pos = i;
            while (true)
            {
                sum += op[pos];
                pos++;
                pos = pos%n;
                if (sum == 50)
                {
                    cnt++;
                    break;
                }
 
                if (sum > 50)
                {
                    break;
                }
            }
        }
 
        ans = cnt > ans ? cnt : ans;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            op[k] = v[i];
            go(k + 1);
            used[i] = false;
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
    v.resize(n);
    op.resize(n);
    used.assign(n, false);
 
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    
    go(0);
 
 
    cout << ans/2 << "\n";
    
 
    return 0;
}