IT 공부방

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

※ 문제

철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.

예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

※ 나의 풀이

먼저 전체 토핑에 대한 종류, 종류별 갯수를 구해준다.

동생이 모든 토핑을 독식했다고 가정하고, 철수가 하나씩 가져왔을때의 상황을 하나씩 비교하였다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    map<int, int> old;
    map<int, int> young;
    int old_type = 0, young_type = 0;
    
    // 동생 값 채워주기
    for(int i = 0; i < topping.size(); i++) young[topping[i]]++;
    young_type = young.size();
    
    // 철수가 하나씩 가져오기
    for(int i = 0; i < topping.size(); i++)
    {
        int idx = topping[i];
        
        if(old[idx] == 0) old_type++;
        old[idx]++;
        
        young[idx]--;
        if(young[idx] <= 0) young_type--;
        
        if(old_type > young_type) break;
        
        if(old_type == young_type) answer++;
    }
    
    return answer;
}

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

※ 문제

콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 n에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.
예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.

은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 초항이 K인 우박수열이 있다면, x = 0일때 y = K이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다.

단, 우박수열 그래프의 가로축 길이를 미리 알 수 없기 때문에 구간의 시작은 음이 아닌 정수, 구간의 끝은 양이 아닌 정수로 표현합니다. 이는 각각 꺾은선 그래프가 시작하는 점과 끝나는 점의 x좌표에 대한 상대적인 오프셋을 의미합니다.

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

※ 나의 풀이

먼저 k가 주어지면 DFS를 통해 그래프 좌표값들을 구해준다.

그리고 각 구간마다의 넓이 값을 저장해놓을 vector를 선언해준 후에 계산을 진행해주었다.

#include <string>
#include <vector>

using namespace std;

void DFS(int k, vector<int> &tmp)
{
	if (k == 1)
	{
		tmp.push_back(k);
		return;
	}
	else
	{
		tmp.push_back(k);
		if (k % 2 == 0)
		{
			DFS(k / 2, tmp);
		}
		else
		{
			DFS(k * 3 + 1, tmp);
		}
	}
}

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    
    	vector<int> graph;
	DFS(k, graph);
	vector<double> graph_area(graph.size() - 1, -1);

	for (int i = 0; i < ranges.size(); i++)
	{
		int rx1 = ranges[i][0];
		int rx2 = graph.size() - 1 + ranges[i][1];

		if (rx2 - rx1 < 0)
		{
			answer.push_back(-1.0);
		}
		else if (rx2 - rx1 == 0)
		{
			answer.push_back(0.0);
		}
		else  // gx2 - gx1 > 0
		{
			double tmp = 0;
			for (int j = rx1; j <= rx2 - 1; j++)
			{
				if (graph_area[j] == -1)
				{
					int gy1 = graph[j];
					int gy2 = graph[j + 1];

					double down = (gy1 > gy2) ? gy2 : gy1;
					double up = (gy1 > gy2) ? gy1 - gy2 : gy2 - gy1;

					graph_area[j] = down + up / 2;

					tmp += down;
					tmp += up / 2;
				}
				else
				{
					tmp += graph_area[j];
				}
			}
			answer.push_back(tmp);
		}

	}
    
    return answer;
}

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

※ 문제

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

 - 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
 - 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

※ 나의 풀이

처음에는 그냥 냅다 for문만 엄청 사용했지만 시간초과가 떴다.

결국 후보군을 추출하여 돌리는 것으로 해결했다.

#include <string>
#include <vector>

using namespace std;

vector<int> check_num(int a)
{
	vector<int> res;

	for (int i = 2; i <= a; i++)
	{
		if (a % i == 0) res.push_back(i);
	}

	return res;
}

int get_result(vector<int> numbers, vector<int> arrayA, vector<int> arrayB)
{
	int answer = 0;
	int a_check = 0, b_check = 0;
	for (int i = 0; i < numbers.size(); i++)
	{
		int num = numbers[i];
		a_check = 0; b_check = 0;
		for (int j = 0; j < arrayA.size(); j++)
		{
			if (arrayA[j] % num != 0)
			{
				a_check++;
			}
		}

		for (int j = 0; j < arrayB.size(); j++)
		{
			if (arrayB[j] % num != 0)
			{
				b_check++;
			}
		}

		if (a_check == 0 && b_check != 0 && b_check == arrayB.size()) answer = num;
		if (a_check != 0 && b_check == 0 && a_check == arrayA.size()) answer = num;
	}

	return answer;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int answer1 = 0, answer2 = 0;
    
    vector<int> numbers = check_num(arrayA[0]);
    answer1 = get_result(numbers, arrayA, arrayB);

    numbers = check_num(arrayB[0]);
    answer2 = get_result(numbers, arrayA, arrayB);

    answer = max(answer1, answer2);
    
    return answer;
}

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

 ※ 문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

※ 나의 풀이

푸는 방법은 두가지가 있을것 같다.

첫번째는 귤 크기마다 몇개씩 있는지 정렬 또는 DFS를 이용해서 풀면 될 것 같다.

 - 정렬

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

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
    
	// map으로 종류 횟수 저장
	map<int, int> tmp;
	for (int i = 0; i < tangerine.size(); i++)
	{
		tmp[tangerine[i]]++;
	}

	// 횟수 기준으로 정렬
	vector<pair<int, int>> vtmp;
	for (pair<int, int> t : tmp)
	{
		vtmp.push_back(make_pair(t.first, t.second));
	}
	sort(vtmp.begin(), vtmp.end(), cmp);
    
	// 정답 구해주기
	int sa = k;
	int answer = 0;
	for (int i = 0; i < sa; i++)
	{
		if (k <= 0) break;
		else
		{
			k -= vtmp[i].second;
			answer++;
		}
	}
    
    return answer;
}

 - DFS → 시간초과 발생

#include <string>
#include <vector>

using namespace std;

int answer;
vector<int> tangerine;

void DFS(int idx, int cnt, vector<int> res, vector<int> ch_idx_tan, vector<int> ch_tan)
{
	if (idx == res.size())
	{
		if (answer > cnt)
		{
			answer = cnt;
		}
	}
	else
	{
		for (int i = 0; i < tangerine.size(); i++)
		{
			if (ch_idx_tan[i] == 0)	// 사용한 tangerine의 idx 체크
			{
				ch_idx_tan[i] = 1;
				res[idx] = tangerine[i];
				
				if (ch_tan[tangerine[i]] == 0)	// 새로운 숫자면 cnt++
				{
					ch_tan[tangerine[i]]++;
					DFS(idx + 1, cnt + 1, res, ch_idx_tan, ch_tan);
					ch_tan[tangerine[i]]--;
				}
				else  // ch_tan[tangerine[i]] != 0
				{
					ch_tan[tangerine[i]]++;
					DFS(idx + 1, cnt, res, ch_idx_tan, ch_tan);
					ch_tan[tangerine[i]]--;
				}

				ch_idx_tan[i] = 0;
			}
		}
	}
}

int solution(int k, vector<int> tangerin) {
    answer = 2147000000;
    tangerine = tangerin;
    
    vector<int> res(k, 0);
	vector<int> ch_tan(tangerine.size(), 0);		// 숫자별 사용 횟수
	vector<int> ch_idx_tan(tangerine.size(), 0);	// tan에서 사용한 인덱스 체크
	DFS(0, 0, res, ch_idx_tan, ch_tan);
    
    return answer;
}

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

※ 문제

프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

※ 나의 풀이

치려는 공을 상하좌우로 대칭시켜서 피타고라스로 거리 측정하면 끝!

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

using namespace std;

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    
    vector<int> ball;
	int tmp = 2147000000;
	int res = 2147000000;
	int x = 0, y = 0;
	for (int i = 0; i < balls.size(); i++)
	{
		ball = balls[i];
		res = 2147000000;
		// 상
		x = ball[0] - startX;
		y = n + (n - ball[1]) - startY;
        if(!(x == 0 && ball[1] > startY))
        {
            tmp = pow(x, 2) + pow(y, 2);
			if (res > tmp) res = tmp;
        }

		// 하
		x = ball[0] - startX;
		y = startY - -1 * ball[1];
        if(!(x == 0 && ball[1] < startY))
        {
            tmp = pow(x, 2) + pow(y, 2);
			if (res > tmp) res = tmp;
        }

		// 좌
		x = startX - -1 * ball[0];
		y = ball[1] - startY;
        if(!(y == 0 && ball[0] < startX))
        {
            tmp = pow(x, 2) + pow(y, 2);
			if (res > tmp) res = tmp;
        }

		// 우
		x = m + (m - ball[0]) - startX;
		y = ball[1] - startY;
        if(!(y == 0 && ball[0] > startX))
        {
            tmp = pow(x, 2) + pow(y, 2);
			if (res > tmp) res = tmp;
        }
        
        answer.push_back(res);
    }
    
    return answer;
}

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

※ 문제

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

※ 나의 풀이

이 문제는 그렇게 어렵지 않았다.

BFS 관련 응용 문제이지만 한 칸씩 이동하는 것이 아닌 미끄러져 이동하는 것이다.

미끄러져 이동하는 것은 while문을 이용하여 D를 만나거나 map 끝에 다다르거나 할때 멈추면 된다.

여기에서 주의할 점은 G (목표)를 만난다고 해서 멈출 수 있는게 아니라는 것이다.

	// 상하좌우
	vector<int> di = { -1, 1, 0, 0 };
	vector<int> dj = { 0, 0, -1, 1 };

	// 맵 바꿔주기 및 시작위치, 종료위치 저장해주기
	vector<vector<char>> map;
	vector<vector<int>> ch_map(board.size(), vector<int>(board[0].size(), 2147000000));
	pair<int, int> S, G;
	vector<char> tmp;
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[i].size(); j++)
		{
			if (board[i][j] == 'R') S = make_pair(i, j);
			else if (board[i][j] == 'G') G = make_pair(i, j);
			else if (board[i][j] == 'D') ch_map[i][j] = 2146999999;
			tmp.push_back(board[i][j]);
		}
		map.push_back(tmp);
		tmp.clear();
	}
	ch_map[S.first][S.second] = 0;

	// 경로 찾기
	queue<pair<int, int>> q;
	q.push(S);
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		int i = 0;
		int xx, yy;
		for (i = 0; i < 4; i++)
		{
			xx = x;
			yy = y;
			while (1)
			{
				xx += di[i];
				yy += dj[i];
				if (xx < 0 || yy < 0 || xx >= map.size() || yy >= map[0].size()) break;
				if (map[xx][yy] == 'D') break;
			}
			xx -= di[i];
			yy -= dj[i];

			if (ch_map[xx][yy] != 2147000000) continue;
			ch_map[xx][yy] = min(ch_map[xx][yy], ch_map[x][y] + 1);
			q.push(make_pair(xx, yy));
		}
	}

	answer = ch_map[G.first][G.second];

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

※ 문제

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

 - 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
 - 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
 - 광물은 주어진 순서대로만 캘 수 있습니다.
 - 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

※ 나의 풀이

DFS로 접근하기로 했다.

일단 DFS의 인자값으로 사용되는 것은

처리해야할 minerals 인덱스 값, 피로도합, 사용한 곡괭이 수 이렇게 3개의 인자가 들어가게 된다.

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

using namespace std;

vector<string> minerals;
vector<int> picks;
vector<vector<int>> tired =
{
	{1, 1, 1},
	{5, 1, 1},
	{25, 5, 1}
};
int rres = 2147000000;

void DFS(int m_idx, int res, int sum)
{
	if (m_idx >= minerals.size() || sum == 0)
	{
		rres = min(rres, res);
		return;
	}
	else
	{
		int idx, j;
		int tmp = 0;
		for (int i = 0; i < picks.size(); i++)
		{
			tmp = 0;
			if (picks[i] != 0)
			{
				for (j = 0; j < 5; j++)
				{
					if (m_idx + j >= minerals.size())
					{
						break;
					}
					else
					{
						if (minerals[m_idx + j] == "diamond") idx = 0;
						else if (minerals[m_idx + j] == "iron") idx = 1;
						else idx = 2;
						tmp += tired[i][idx];
					}
				}

				picks[i]--;
				DFS(m_idx + j, res + tmp, sum - 1);
				picks[i]++;
			}
		}
	}
}

int solution(vector<int> pick, vector<string> mineral) {
    int answer = 0;
    
    minerals = mineral;
    picks = pick;
    int sum = 0;
	for (int i = 0; i < picks.size(); i++)
	{
		sum += picks[i];
	}
    
	DFS(0, 0, sum);
    answer = rres;
    
    return answer;
}

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

※ 문제

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

※ 나의 풀이

이 문제는 평범한 구현 문제 같았다.

다만, 구현하기 굉장히 귀찮은 문제이다.

부등호 하나를 잘못적용해서 시간을 엄청 잡아먹었다...

struct Edge
{
	string subject;
	int start_time = 0, need_time = 0;

	Edge(string s, string t, string n)
	{
		subject = s;
		start_time = s2i(t);
		need_time = stoi(n);
	}

	Edge(string s, int t, int n)
	{
		subject = s;
		start_time = t;
		need_time = n;
	}

	int s2i(string time)
	{
		int hour = stoi(time.substr(0, 2));
		int minute = stoi(time.substr(3, 5));
		return hour * 60 + minute;
	}

	bool operator<(const Edge a) const
	{
		return start_time < a.start_time;
	}
};

	vector<string> answer;

	// 과목 정렬
	vector<Edge> info;
	for (int i = 0; i < plans.size(); i++)
	{
		info.push_back(Edge(plans[i][0], plans[i][1], plans[i][2]));
	}
	sort(info.begin(), info.end());

	// 잔여 과목 저장소
	stack<Edge> st;

	// 과목 처리하기
	int extra_time = 0;
	for (int i = 0; i < info.size() - 1; i++)
	{
		Edge cur = info[i];
		Edge next = info[i + 1];
		extra_time = next.start_time - cur.start_time;

		if (extra_time == 0)
		{
			answer.push_back(cur.subject);
			continue;
		}

		if (extra_time < cur.need_time)
		{
			st.push(Edge(cur.subject, cur.start_time, cur.need_time - extra_time));
		}
		else // extra_time >= cur.need_time
		{
			answer.push_back(cur.subject);
			extra_time -= cur.need_time;
			while (!st.empty() && extra_time != 0)
			{
				if (extra_time >= st.top().need_time)
				{
					extra_time -= st.top().need_time;
					answer.push_back(st.top().subject);
					st.pop();
				}
				else // extra_time < st.top().need_time
				{
					st.top().need_time -= extra_time;
					break;
				}
			}
		}
	}
	answer.push_back(info[info.size() - 1].subject);

	while (!st.empty())
	{
		answer.push_back(st.top().subject);
		st.pop();
	}