정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
※ 나의 풀이
처음에는 무작정 풀이 했지만 절반 이상이 시간초과가 발생했다.
그래서 배열의 규칙을 찾았다.
반복문의 범위를 left ~ right로 설정한다.
행 = i / n
열 = i % n
행 >= 열 → 행 + 1
행 < 열 → 열 + 1
위의 규칙으로 진행하면 해결된다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n, long long left, long long right) {
vector<int> answer;
int row = 0, col = 0, tmp = 0;
for (long long i = left; i <= right; i++)
{
row = i / n;
col = i % n;
tmp = (row >= col) ? row + 1 : col + 1;
answer.push_back(tmp);
}
return answer;
}
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
※ 나의 풀이
모든 경우의 수를 고려해야 하므로, DFS를 이용하여 문제 풀이를 진행했다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> dg;
int K = 0, answer = 0;
vector<bool> ch;
void DFS(int answer_cnt, int kk)
{
if (kk < 0) return;
answer = max(answer, answer_cnt);
for (int i = 0; i < ch.size(); i++)
{
if (!ch[i] && kk >= dg[i][0])
{
ch[i] = true;
DFS(answer_cnt + 1, kk - dg[i][1]);
ch[i] = false;
}
}
}
int solution(int k, vector<vector<int>> dungeons) {
K = k;
dg = dungeons;
for (int i = 0; i < dg.size(); i++) ch.push_back(false);
// DFS로 접근하기
DFS(0, K);
return answer;
}
