프로그래머스 Level 2 : 피로도 C언어

▶문제 : 코딩테스트 연습 - 피로도 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 피로도

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int check[8];//던전에 들어갔는지 체크하는 배열
int cnt;//최대 던전 개수

void dfs(int k, int **dungeons, int rows, int n) {//n : 던전에 들어간 횟수
    if (cnt < n) cnt = n;//최대 던전 개수보다 n이 크다면 n대입

    for (int i = 0; i < rows && cnt < rows; i++) {//모든 던전 탐색&&cnt가 던전 총 개수보다 작을 때
        if (check[i] == 0 && dungeons[i][0] <= k) {//안들어간 던전인지 확인&&최소 필요 피로도 확인
            check[i] = 1;//들어갔다는 체크
            dfs(k - dungeons[i][1], dungeons, rows, n + 1);//피로도 소모,던전에 들어간 횟수 +1
            check[i] = 0;//초기화
        }
    }
}

// dungeons_rows는 2차원 배열 dungeons의 행 길이, dungeons_cols는 2차원 배열 dungeons의 열 길이입니다.
int solution(int k, int **dungeons, size_t dungeons_rows, size_t dungeons_cols) {
    dfs(k, dungeons, dungeons_rows, 0);//n=0부터 시작
    return cnt;
}

 

▶해석

정렬해서 풀어야 할지 필요 피로도와 소모 필요도를 고려해 정렬할지 고민하던 중 2차원 배열 dungeons의 행 길이가 1 이상 8 이하라는 조건을 확인해 전체 탐색을 해도 되겠다고 생각했다.

 

check 배열을 선언해 던전에 들어갔는지 체크하였다.

cnt는 최대 던전 개수이다.

 

전체 탐색을 위해 재귀 함수 dfs를 만들어 주어진 매개변수에 n을 추가하였다.

n은 던전에 들어간 횟수를 계산한다.

 

if문으로 최대 던전 개수를 n과 비교해 대입하였다.

 

for문으로 모든 던전을 반복하고, cnt가 모든 던전의 개수와 같다면 종료하도록 하였다.

if문에서는 check배열로 들어갔던 던전인지 체크하여 0이면 들어가지 않았으므로 참이고,

던전에 들어가기 위한 최소 필요도를 확인한다.

if문이 참이 되면 들어가도 되는 던전이므로 check [i] = 1; 로 들어갔다는 표시를 해준다.

다음 던전을 들어가기 위해 재귀 함수를 호출하고, k가 피로도이므로 소모 피로도를 뺀다.

또한 n이 던전에 들어간 횟수이므로 +1을 해준다.

마지막으로 재귀 함수가 끝나면 다른 던전에 먼저 들어간 경우를 확인해야 하므로 초기화해준다.