[알고리즘풀이]백준 6236 : 용돈 관리 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 6236번 용돈 관리를 풀게 되었습니다.

6236번: 용돈 관리

 

본문

1) 문제

 

2) 과정

이 문제는 꽤 고전했던 문제입니다. 한 2일?정도 시간이 걸렸던거 같아요. 문제 이해도 쉽지않았고, 분명 예제 문제는 잘 풀리는데 체점만 돌리면 에러가 나서 이를 보완하느라 기간이 필요했습니다. 정답률을 보면 30퍼센트인 것 부터 다들 쉽지 않았었나봅니다... 

 

코드는 input, func, testFunc로 구성했어요. func는 재귀를 이용해 범위 내의 값을 testFunc에 넣으며 범위를 좁혀 나가는 함수이고, testFunc는 해당 금액으로 지정된 날을 살 수 있는지를 확인하는 함수입니다.

 

2-1) main

 

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(func(startVal,endVal));
    }

main은 input함수와 func함수를 실행하고 그 결과값을 리턴하는 출력문으로 구성됩니다. func의 파라미터인 startVal과 endVal은 input에서 일 사용금액 중 가장 큰 값을 startVal, 모든 금액의 합계를 endVal로 설정했습니다.

 

2-2) input

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n = Integer.parseInt(strArr[0]);
        m = Integer.parseInt(strArr[1]);

        intArr = new int[n];
        for(int i =0;i<n;i++) {
            intArr[i]=Integer.parseInt(reader.readLine());
            startVal = Math.max(intArr[i], startVal);
            endVal += intArr[i];
        }

    }

 

input함수를 볼때는 해당 글을 참고하시면 이해하기 쉽습니다.

[개념정리] System.in / InputStreamReader / BufferedReader 정리

 

금액을 사용할 날을 의미하는 n과 인출할 횟수를 의미하는 m을 첫줄에서 받아오고,

이후 n번만큼 금액을 받아 intArr에 저장하며 main에서 설명한 startVal과 endVal의 값을 저장합니다.

 

 

2-3) func

    private static int func(int start, int end){
        if(start>end)  return start;
        if(testFunc((end+start)/2)) return func(start,((end+start)/2)-1);
        else return func(((end+start)/2)+1,end);
    }

 재귀를 좋아하는 저 코찔이답게 이번에도 재귀를 사용했습니다. start의 값이 end보다 커질때까지 testFunc의 가능한지 불가능한지에 대한 리턴값에 따라 출금한 횟수가 더 적으면 if문으로, 더 많으면 else문으로 범위를 좁혀나가도록 했습니다.

 그리고 가장 많이 사용된 값인 (end+start)/2는 시작값과 종료값의 딱 중간값을 의미하고, 출금횟수가 적어 더 늘려나가야할 때는 현재 start지점부터 중간값(end+start)/2보다 1작은 지점까지를 범위로 재귀를 돌게하고 반대일 경우는 중간값보다 1 많은 지점부터 end지점까지 범위로 재귀를 돌게했습니다.

 추가로 왜 start==end가 아닌 start>end인지 궁금해하실 분들이 있을지도 모른다는 생각에 제가 저렇게 구현한 이유를 설명하자면, if-else문을 보시면 넣어주는 파라미터에 중간값을 넣는게 아닌 +1 혹은 -1을 해줍니다. 그렇기 때문에 시작값과 중간값 혹은 중간값과 종료값이 같다면 if-else문의 func함수가 실행되면 start는 end보다 1커질 수 밖에 없습니다. 그래서 start==end로 종료조건을 맞춘 것이 아닌 start>end로 종료조건을 맞춘 것입니다.

 

2-4) testFunc

    private static boolean testFunc(int money){
        int repo=0, count=1;
        for(int i =0;i<n;i++){
            if(repo+intArr[i]>money){
                repo=0;
                count++;
            }
            repo+=intArr[i];
        }
        if(repo==0) count--;
        return count <= m;
    }

아마 이 문제의 핵심 로직이 아닐까 싶은데요... 이 부분이 자꾸 틀려서 꽤 애를 먹었습니다.

먼저 변수를 설명하자면 repo는 money가 될때까지 사용한 금액을 모으는 변수이고, count는 돈을 인출한 횟수입니다. 그리고 파라미터로 받은 money는 func에서 넣어준 중앙값, 즉 "이 금액이 가능해?"라고 물어 범위를 좁혀나가기 위한 시험값입니다. repo는 아직 사용한 값이 없기 때문에 0, count는 어떠한 큰 값을 넣든 무조건 1번은 인출을 하기 때문에 1로 값을 넣어줬습니다.

 

for문에서는 지금껏 사용한 돈과 써야하는 돈의 합이 한번 인출해서 얻어올 수 있는 값보다 크다면(지금껏 사용한 금액에 이번에 사용한 금액까지 더해지면 새로 돈을 출금해야하기 때문) 사용한 돈을 초기화하고 인출횟수를 1 증가시킵니다. 그리고 if문을 지났든 안지났든 하루가 지났기 때문에 repo에 그날 사용한 금액을 추가해줍니다. 

 

그렇게 모든 날이 다 지났다면, 사용한 금액이 아예 없을 경우 인출을 아예안한 것이기 때문에 초반에 넣어줬던 1을 제외하기 위해 if(repo==0) count--;를 넣어줍니다. 

 

그리고 인출한 횟수가 출금을 원했던 횟수인 m보다 작거나 같으면 true를 아니라면 false를 리턴하게 합니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    private static int n,m,startVal,endVal;
    private static int[] intArr;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n = Integer.parseInt(strArr[0]);
        m = Integer.parseInt(strArr[1]);

        intArr = new int[n];
        for(int i =0;i<n;i++) {
            intArr[i]=Integer.parseInt(reader.readLine());
            startVal = Math.max(intArr[i], startVal);
            endVal += intArr[i];
        }

    }

    private static int func(int start, int end){
        if(start>end)  return start;
        if(testFunc((end+start)/2)) return func(start,((end+start)/2)-1);
        else return func(((end+start)/2)+1,end);
    }

    private static boolean testFunc(int money){
        int repo=0, count=1;
        for(int i =0;i<n;i++){
            if(repo+intArr[i]>money){
                repo=0;
                count++;
            }
            repo+=intArr[i];
        }
        if(repo==0) count--;
        return count <= m;
    }

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(func(startVal,endVal));
    }

}

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/binarySearch/BOJ6236.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비