백트래킹

1. 프로그래머스 2022 Kakao Blind Recruitment 양궁대회

 

프로그래머스

풀이1️⃣ - 오답

// 라이언 b vs 어피치 a
// 규칙: a>=b면 어피치가 k점, a<b면 라이언이 k점
// 규칙: a==b==0이면 k점 못가져감
// 규칙: 최종 점수가 같으면 어피치가 우승

// info: 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열

// 출력: 라이언이 우승하기 위해 n발의 화살을 어떤 과녁 점수에 낮혀야 하는지 answer 배열에 담아 리턴하기 (라이언 우승 못하는 경우 -1을 배열에 넣어서 리턴) (라이언이 큰 점수차로 우승할 방법이 여러 개면 가장 낮은 점수를 더 많이 맞힌 경우 리턴)

// 알고리즘: dfs를 이용한 완전탐색
// 0-10점까지 11개의 점수를 획득할지 안할지 결정하자
// 획득할거면 어피치보다 1개의 화살을 더 맞춰야 하고, 획득하지 않는다면 화살을 맞추지 않아도 됨 -> 2^11의 경우가 존재

#include <string>
#include <vector>

using namespace std;

int arr[11];
int max_diff = 0;

vector<int> ryan(11, 0);
vector<int> apeach;
vector<int> answer = { -1 };

int cmp(vector<int> ryan, vector<int> apeach) {
    int ryan_score = 0;
    int apeach_score = 0;

    for (int i = 0; i < 11; i++) {
        if (ryan[i] > apeach[i]) {
            ryan_score += 10 - i;
        }
        else {
            if (apeach[i] != 0) {
                apeach_score += 10 - i;
            }
        }
    }

    return ryan_score - apeach_score;
}

void shooting(int depth, int num, int n) {
    if (depth == n) {
        vector<int> v;
        for (int i = 0; i < n; i++) {
            v.push_back(arr[i]);
        }

        for (int i = 0; i < n; i++) {
            ryan[10 - v[i]]++;
        }

        int diff = cmp(ryan, apeach);

        if (diff > max_diff) {
            max_diff = diff;
            answer = ryan;
        }

        return;
    }

    for (int i = num; i < 11; i++) {
        arr[depth] = i;
        shooting(depth + 1, i, n);
    }
}

vector<int> solution(int n, vector<int> info) {
    apeach = info;
    shooting(0, 0, n);

    return answer;
}

 

---

 

2. 백준 9663 N-Qeen

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

 

풀이1️⃣ - 정답

// 입력: 체스판의 크기 및 퀸의 수 N
// 출력: 퀸 N개를 공격할 수 없게 놓는 경우의 수

// 한 행당 하나의 퀸만 존재 가능 -> 스도쿠 마냥
// 일차원 배열에 일단 퀸을 저장해주고 한 행씩 퀸을 옮겨가며 배치


#include <iostream>
#define MAX 15
using namespace std;

int col[MAX];
int N, total=0;

bool check(int level){
    for (int j=0;j<level;j++){
        // 대각선이거나 같은 라인
        if (col[j] == col[level] || abs(col[level]-col[j]) == level-j) return false;
    }
    return true;
}

void nqueen(int x){
    if (x==N){
        total++;
    } else {
        for (int i=0;i<N;i++){
            col[x] = i;
            if (check(x)) nqueen(x+1); // 퀸의 자리를 옮겨주며 퀸 배치
        }
    }
}

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

    cin >> N;
    nqueen(0);
    cout << total;

    return 0;
}