백준 25194번 결전의 금요일 C++ (골드5)

https://www.acmicpc.net/problem/25194

 

주어진 수들을 더하는 경우중에 7로 나누었을때 나머지가 4가 되는 경우가 있으면 목요일에 일을 끝내고 금요일에 헬스장을 갈 수 있다.

 

결국 나머지를 구하는 문제이기 때문에 주어진 수들을 7로 나눈 나머지들을 저장하여 나머지가 1~6인 경우의 수가 몇개인지로 관리하였다. 만약 7로 나누었을때 나머지가 0이면 더해도 의미가 없는 숫자이기 때문에 제외했다.

 

그리고 백트래킹을 통해 가능한 경우를 탐색하여 7로 나누었을때 나머지가 4인 경우를 찾았는데, 사실 7로 나누기 전의 숫자들로 백트래킹을 진행하면 숫자의 경우가 최대 1000개이기때문에 시간초과가 난다.

 

하지만 7로 나눈 나머지를 통해 1~6이 몇개인지로 관리하고 있기 때문에 정렬이 되어있는 상태이고 가능하다면 조금만 백트래킹을 돌려도 7로 나누었을때 4가 되는 경우는 나온다. 찾은뒤부터는 바로 return을 하여 필요없는 탐색은 하지 않는다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<int> v(7, 0);

bool ans = false;

void BT(int val) {
    if (ans) return;
    if (val % 7 == 4) {
        ans = true;
        return;
    }
    for (int i = 1; i <= 6; i++)
    {
        if (v[i] == 0) continue;
        v[i]--;
        BT(val + i);
        v[i]++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        if (a % 7 == 0) continue;
        v[a % 7]++;
    }
    BT(0);
    if (ans) cout << "YES";
    else cout << "NO";
}