백준 및 코드포스

https://school.programmers.co.kr/learn/courses/30/lessons/172927

브루트포스로 풀었다.

사용할 곡괭이 딱 10개만 정해서 백트래킹으로..

다른 사람들 풀이 보니까 그리디가 있긴 했는데, '이렇게 명백한 백트래킹에선 빠르게 백트래킹 구현하는게 낫지 않나?' 싶다.

백트래킹 코드야 워낙에 정형화 되어있으니, 손가락만 빠르다면 그리디보다 더 효과적일 것 같다.. ㅋㅋ

이것만 떡하니 올리긴 뭐해서 챗지피티한테 코드 설명만 부탁해서 첨부하겠다~

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> allPicks;
vector<string> allMinerals;
int arr[10];
int brr[10];
bool isused[10];
int picksSum;
int tiredSum = 99999999;

void func(int k) {
    if(k == picksSum) {
        int tempTiredSum = 0;
        for(int i = 0; i < allMinerals.size(); i++) {
            if(brr[i / 5] == 0) {
                break;
            }
            if(allMinerals[i][0] == 's') tempTiredSum += 1;
            else {
                if(brr[i / 5] == 3 && allMinerals[i][0] == 'd') tempTiredSum += 25;   
                if(brr[i / 5] == 3 && allMinerals[i][0] == 'i') tempTiredSum += 5;   
                if(brr[i / 5] == 2 && allMinerals[i][0] == 'd') tempTiredSum += 5;   
                if(brr[i / 5] == 2 && allMinerals[i][0] == 'i') tempTiredSum += 1;   
                if(brr[i / 5] == 1 && allMinerals[i][0] == 'd') tempTiredSum += 1;   
                if(brr[i / 5] == 1 && allMinerals[i][0] == 'i') tempTiredSum += 1;   
            }
        }
        tiredSum = min(tiredSum, tempTiredSum);
        return;
    }
    
    for(int i = 0; i < picksSum; i++) {
        if(!isused[i]) {
            brr[k] = arr[i];
            isused[i] = 1;
            func(k + 1);
            isused[i] = 0;
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    allPicks = picks;
    allMinerals = minerals;
    int coun = 0;
    picksSum = min(10, picks[0] + picks[1] + picks[2]);
    for(int i = 0; i < 3; i++) {
        while(picks[i]) {
            arr[coun++] = i + 1;
            picks[i]--;
            if(coun == 10) break;
        }
        if(coun == 10) break;
    }
    
    func(0);
    
    return tiredSum;
}

이 코드는 주어진 광물을 캐기 위해 곡괭이를 조합하는 모든 경우의 수를 탐색하여 최소한의 피로도를 구하는 함수인 solution을 구현한 코드입니다.

코드에서 사용되는 변수들은 다음과 같습니다:

• allPicks: 다이아몬드, 철, 돌 곡괭이의 개수를 담은 벡터
• allMinerals: 광물들의 순서를 담은 문자열 벡터
• arr: 모든 곡괭이 종류를 포함하는 배열
• brr: 현재 선택한 곡괭이들을 저장하는 배열
• isused: 곡괭이가 사용되었는지 여부를 나타내는 배열
• picksSum: 곡괭이 종류의 총 개수를 저장하는 변수
• tiredSum: 최소 피로도를 저장하는 변수

주요 함수:

1. func(int k): 재귀적으로 모든 곡괭이를 선택하는 함수. k는 현재 선택한 곡괭이의 개수를 나타냅니다. 모든 곡괭이를 선택한 경우에는 해당 조합에 대한 피로도를 계산하고, 최소 피로도인 tiredSum을 갱신합니다.
2. solution(vector<int> picks, vector<string> minerals): 주어진 광물을 캐기 위해 가능한 모든 곡괭이 조합을 구하여 최소한의 피로도를 반환하는 함수입니다. 입력으로 주어진 picks 벡터에서 다이아몬드, 철, 돌 곡괭이의 개수를 읽어와 arr 배열에 모든 곡괭이 종류를 저장합니다. 그리고 func(0)을 호출하여 모든 곡괭이 조합을 탐색하고 최소 피로도를 구합니다.

코드에서 func 함수를 통해 재귀적으로 모든 곡괭이 조합을 탐색하고, 각 조합에 대해 광물을 캐기 위한 피로도를 계산하고 최소 피로도를 구하게 됩니다. 이를 통해 모든 광물을 캐기 위한 최소한의 피로도를 반환합니다.

기분 낼 겸 오랜만에 프로그래머스.. 풀어봤다.

카카오 테크 캠퍼스 붙고나서 온전히 개발에만 몰두했기에....... 거의 5개월만인듯 하다..

https://school.programmers.co.kr/learn/courses/30/lessons/181188

간단히 그리디하게 풀 수 있는 문제다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare(vector<int> &a, vector<int> &b) {
    if(a[0] != b[0]) {
        return a[0] < b[0];
    } else {
        return a[1] < b[1];
    }
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end(), compare);

    for(int i = 0; i < targets.size();) {
        int last = targets[i][1];

        while(i < targets.size() && last > targets[i][0]) {
            last = min(targets[i][1], last);
            i++;
        }
        answer++;
    }
    return answer;
}

먼저, 정렬을 해준다.

인덱스 i를 이용해서 targets 벡터를 하나씩 확인한다. 현재 미사일의 끝점을 last에 저장한다.

while로 현재 미사일의 끝점 last가 다음 미사일의 시작점보다 크면 계속해서 다음 미사일을 확인한다.

만약 현재 미사일의 끝점이 다음 미사일의 시작점보다 크다면, 두 미사일은 한 번에 요격 가능하다.

그래서 두 미사일 중 끝점이 더 작은 값을 last로 갱신한다. 이렇게 함으로써 현재 요격 가능한 영역에 포함되는 모든 미사일을 한 번에 요격할 수 있는 것이 보장된다. (그리디하게)

i를 증가시켜 다음 미사일로 넘어가고, while이 끝나면 answer를 1 증가시킨다.

모든 미사일들을 순회하면서 선택된 요격 미사일들의 개수인 answer를 반환한다.

이 값은 모든 폭격 미사일을 요격하기 위해 필요한 최소한의 요격 미사일 수이다..

1, 2, 4로만 이루어진 3진수 체계로 주어진 n을 나타내면 되는 문제입니다.

어떻게 해결해야 할까 고민 많이 했는데, 노트에 적어보면서 규칙을 찾을 수 있었습니다.

거꾸로 생각했을 때,

answer = "124" 인 경우

$n = 18$일 때 answer = "124" 임을 도출할 수 있었고,

1. n % 3 이 각각 0, 1, 2일 때 뒷자리가 4, 1, 2 임을 알 수 있었습니다.

그다음 규칙을 찾는 것이 어려웠는데,

$n = \frac{(n - 1)}{3}$

2. 위와 같이 적용했을 때, 1번이 다시 적용됨을 알 수 있었습니다.

위와 같이 문자열을 만들어주면 거꾸로 저장이 되니까,

return 전에 완성된 문자열을 뒤집어주면 정답입니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(int n) {
    string answer = "";
    while(n) {
        int tem = n % 3;
        if(tem == 1) answer += "1";
        else if(tem == 2) answer += "2";
        else if(tem == 0) answer += "4";

        n = (n - 1) / 3;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

보잘것없는 문제 정답 도출까지의 제 필기입니다.