[BOJ - JAVA] 22864 - 피로도 (브루트 포스)

# 주소

https://www.acmicpc.net/problem/22864

22864번: 피로도

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int a,b,c,d;
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        a = scan.nextInt();
        b = scan.nextInt();
        c = scan.nextInt();
        d = scan.nextInt();
        dfs(0,0, 0);
        System.out.println(max);
    }
    //5 3 2 10
    static void dfs(int time, int work,int tired){
        if(time <= 24) {
            if(tired < 0)
                tired = 0;
            if(tired > d){
                return;
            }
            dfs(time + 1, work + b, tired + a);
            dfs(time + 1, work, tired - c);
            max = Math.max(max, work);
        }
    }
}

류호석님의 필수 브루트포스 문제중의 하나입니다.

삼성SW역량 브루트포스 문제를 풀다가 너무 어려워서 현타가 오는 바람에 기초부터 다시 다져올라가기로 마음먹었습니다.

이 앞전에 설명드린 브루트포스 문제는 겨우겨우 이해하고 풀어서 제출했는데 17135번의 캐슬 디펜스 https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

이 문제를 푸는데 하 진짜 눈물이 나더라구요.

분명 풀 수 있을 것 같은데 어디가 잘못됐는지 모르겠어서 음 이번주내로 브루트포스 다시 완전히 마스터 한 다음에 설명드리도록 하겠습니다. 아자아자... (ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ)

이 문제는 쉬우니까 일단 바로바로 넘어가봅시다.

static int a,b,c,d;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    a = scan.nextInt();
    b = scan.nextInt();
    c = scan.nextInt();
    d = scan.nextInt();
    dfs(0,0, 0);
    System.out.println(max);
}

A,B,C,D를 입력받고 DFS(0,0,0)을 실행합니다.

if(time <= 24) {
    if(tired < 0)
        tired = 0;
    if(tired > d){
        return;
    }

여기에서 time은 24보다 작거나 같을때로 범위를 두는 것이 옳습니다.

그리고 tired가 0보다 작으면 0으로 초기화해주어야 하고 tired가 입력받은 d보다 커지면 return시켜서 탐색하지 않도록 합니다.

dfs(time + 1, work + b, tired + a);
dfs(time + 1, work, tired - c);
max = Math.max(max, work);

그리고 dfs를 재귀함수 2가지로 선택적으로 실행할 수 있게 구현합니다.

먼저 time은 1씩 증가시켜주는 것이 옳습니다.

이유는 1시간 단위로 작업을 진행하기 때문입니다.

그리고 work를 할 수도 있고 안할 수도 있기 때문에, 만약 work를 한다면 tired에는 a를 더해주고 work를 하지 않을 경우, work는 유지시키되 tired는 c를 빼주어서 피로도를 감소시킵니다.

그리고 최종적으로 work가 가장 큰 값을 max에 담아서 출력해주면 그것이 정답이 됩니다.

브루트포스 다시 제대로 다져서 좋은 포스팅으로 올려보겠습니다.

감사합니다.