[BOJ] 1581 락스타 락동호 java

문제

한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공개했다. 하지만, 그 후 락동호는 음악을 접고 체스에 입문하게 되었고, 그 결과 2007년 3월 31일 Heroes원정대에서는 체스 부분으로 참가하게 된다. 그 후 절대로 음악을 하지 않을 것 같았지만, 모두의 예상을 깨고, 2007년 4월 21일 월드 노래자랑으로 신이 내린 가창력으로 우승한 뒤 자취를 감추었다.

하지만 2008년 7월 13일 드디어 락동호가 컴백한다.

락동호는 지난 몇 달간 자신의 신보에 자신의 음악적 능력을 모두 담았고, 이제 몇몇 곡 중 최고의 곡만을 앨범에 담으려고 한다.

락동호는 빠르게 시작해서 빠르게 끝나는 노래를 FF개 만들었고, 빠르게 시작해서 느리게 끝나는 노래를 FS개, 느리게 시작해서 빠르게 끝나는 노래를 SF개, 그리고 느리게 시작해서 느리게 끝나는 노래를 SS개 만들었다.

락동호는 위와 같은 노래 중 총 몇 개를 자신의 새로운 앨범에 넣어야 할지 결정해야 한다. 그리고 당연히 모든 노래는 두 번 이상 앨범에 등장할 수는 없다.

하지만, 락동호는 이제 세계적인 락스타가 아니다. 따라서, 음반사의 엄청난 제한을 지켜서 앨범에 곡을 수록해야 한다. 이번 앨범으로 다시 자신의 지위를 되찾으려고 하는 락동호이기 때문에, 어쩔 수 없이 이 제한을 지키기로 했다.

1. 빠르게 시작하는 노래는 반드시 빠르게 끝나는 노래의 바로 다음에 와야 한다.
2. 느리게 시작하는 노래는 반드시 느리게 끝나는 노래의 바로 다음에 와야 한다.
3. 동호가 녹음한 노래 중 빠르게 시작하는 노래가 한 개라도 있다면, 앨범의 가장 첫 곡은 빠르게 시작하는 곡이어야 한다. 만약, 빠르게 시작하는 노래가 하나도 없다면, 이 제한은 무시해도 된다.

동호는 음반사가 제한한 제한을 지킬 것이다. 하지만, 자신의 수많은 팬들에게 자신이 아직 건재하다는 것을 알리기 위해 음반에 최대한 많은 곡을 넣으려고 한다.

FF, FS, SF, SS가 주어졌을 때, 동호가 음반사의 제한을 어기지 않고, 최대 몇 곡을 실을 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 FF FS SF SS가 순서대로 들어온다. 모든 수는 0보다 크거나 같고, 1,000보다 작거나 같은 정수이고, 적어도 하나의 수는 0보다 크다.

출력

첫째 줄에 정답을 출력한다.

---

풀이

package hyeonsu.boj;

import java.io.*;
import java.util.*;

public class BOJ1581 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int ff, fs, sf, ss, ans;

    public static void main(String[] args) throws IOException {

        //입력
        st = new StringTokenizer(br.readLine());
        ff = stoi(st.nextToken());
        fs = stoi(st.nextToken());
        sf = stoi(st.nextToken());
        ss = stoi(st.nextToken());

        //로직
        //빠르게 시작하는 곡이 존재 하는가?
        if (ff > 0 || fs > 0) {
            ans += ff;
            if (fs > 0) {
                ans += 1;
                fs--;
                ans += ss;
                if (sf > 0) {
                    ans += (sf + fs) - (Math.abs(sf - fs));
                    if (sf > fs) {
                        ans += 1;
                    }
                }
            }
        }
        //빠르게 시작하는 곡이 없을 떄
        else {
            ans += ss;
            if (sf > 0) {
                ans += 1;
            }
        }

        //출력
        System.out.println(ans);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

 

 

 

 

 

완전탐색 문제였지만 문제의 조건을 잘 고려해서 조건을 적절하게 분기하는 문제이다.

 

처음엔 재귀 방식으로 풀었다. 입력값의 범위를 생각을 안했다. 시간복잡도가 O(n^m) 이어서 이건 값이 조금만 커져도 시간초과였다.

 

그래서 다른 분들의 아이디어를 보고 이렇게 풀면 안되는구나 생각했다. 시간복잡도를 처음부터 제대로 고려했다면 이렇게 풀이하지 않았을텐데.. 코드보다 일단 생각하며 그려보고 시간복잡도를 고려하는 습관을 들여야겠다.

 

이 문제는 3번 제한에 따라서 크게 '빠르게 시작하는 노래가 존재하는 경우'와 '빠르게 시작하는 노래가 존재하지 않는 경우'로 나뉜다.

 

그래서 생각해보면 FF나 SS는 각각 빠르게 시작하는 노래가 존재하는 경우가 s1, 존재하지 않는 경우가 s2 상황이라고 했을 때 FF는 s1, SS가 s2 상황일 때 해당 개수만큼 앨범에 추가가 가능하다.

 

그리고 모든 종류의 노래가 있다고 했을 때 가장 많이 넣을 수 있는 방법은 아래와 같다.

 

FF ... + FS + SS ... + SF + FS + SF + FS ... (마지막은 SF가 FS보다 큰지 아니면 작거나 같은지에 따라 1이 +됨.) 이런 방식이다.

 

FS는 FF와 SS를 넣기 위한 징검다리 느낌으로 한개를 앞에 사용해서 이어준다. 그리고 FS와 SF는 서로 체인처럼 엇갈리며 추가될 수 있기 때문에 (FS + SF) - (|FS - SF|) 라는 식이 나오게 된다. 여기서 SF 먼저 시작되는데 SF값이 더 크면 +1만 해주면 된다.