22.05.08. 풀었던 문제들

프로그래머스 lv. 3

​

1. N-Queen

backtrack 문제. 왜 이게 lv3에서..? lv2에 더 어려운 문제가 많은데 흠... 일단 계속 풀자. 그냥 조건에 맞으면 지속 탐색, 그렇지 않다면 return하는 방법 (backtrack)하면 된다. 멍청하게 삽질을 좀 했다.... 피곤하긴 한가보다.

// N-Queen

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

int answer = 0;
vector<int> queen_position;

bool canPlace(int r, int c){
    for(int i = 0; i<r; i++){
        if(queen_position[i] == c || r-i == abs(c-queen_position[i])) return false;
    }
    return true;
}

void DFS(int cur_depth, int max_depth){
    if(cur_depth == max_depth){
        answer++;
        return;
    }
    
    for(int i = 0; i<max_depth; i++){
        if(canPlace(cur_depth, i)){
            queen_position[cur_depth] = i;
            DFS(cur_depth+1, max_depth);
        }
    }
}

int solution(int n) {
     // queen_position[i] = x일 때 (i,x)에 있다는 것.
    vector<int> qp(n); queen_position = qp;
    DFS(0, n);
    
    return answer;
}

// queen은 줄에 1개씩 둘 수 있다. -> 층은 n개만 가능.

 

2. 하노이의 탑

유명하디 유명한 재귀 문제. 오랜만에 풀어봐서 잘 될까 싶었는데 잘 된다.

// 하노이의 탑

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;

// size 1짜리를 from에서 temp를 써서 to로 옮기는 함수.
void move(int from, int temp, int to, int size){
    // 만약 원판 사이즈가 1이면 temp 쓰지 않아도 됨
    if(size == 1){
        answer.push_back({from, to});
        return;
    }
    
    // size-1짜리를 from에서 temp로 옮기고
    move(from, to, temp, size-1);    
    // size짜리를 from에서 to로
    answer.push_back({from, to});
    // size-1짜리를 temp에서 to로 옮김
    move(temp, from, to, size-1);
}

vector<vector<int>> solution(int n) {
    move(1, 2, 3, n);
    return answer;
}

 

 

3. 최고의 집합

보통 이런 문제가 나온다면

x + y + ... + a = s일 때, 미지수 개수는 n개, 모두 자연수여야 함. -> 다음과 같이 변경

x' + y' + ... + a' = s-n이고 미지수 개수는 n개, 모든 미지수 >= 0이어야 함

즉, (s-n)개의 (동일한)1을 n개의 미지수에 중복 있이, 순서 없이 넣는 방법의 수이므로 중복조합이다.

근데 x' <= y' <= ... <= a'이고, s-n개를 n개에 배분하는 경우의 수 - > nH(s-n)이다.

그러나 이 문제... 1만H1억의 경우를 모두 계산할 수 있을까?

NO! 수학적 접근이 필요하다... 고등학교 과정에서 x + y = n일 때, xy의 값이 최대가 되는 xy의 값은? 이런 미분 문제에서 알 수 있듯 x = y = n/2일 때 최대다. 이게 일반화되면 x1 + x2 + ... + xk = n일 때 x1 * x2 * ... * xk가 최대가 되는 값은 x1 = x2 = ... = xk = n/k이다. 이 내용에 따라 코드를 구현하면 된다. 다만 자연수만 허용되므로 나머지가 있는 경우 뒤에서부터 1씩 더해준다.

// 최고의 집합

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    if(s/n == 0) return {-1};
    
    vector<int> answer(n, s/n);
    int r = s%n;
    for(int i = n-1; i>=0; i--){
        if(r == 0) break;
        r--; answer[i]++;
    }
    return answer;
}