[백준] 1581번 - 락스타 락동호 (Gold 4)

문제 링크

백준 1581번 - 락스타 락동호 (Gold 4)

문제 설명

빠르게 시작해서 빠르게 끝나는 노래가 FF개, 빠르게 시작해서 느리게 끝나는 노래가 FS개, 느리게 시작해서 빠르게 끝나는 노래가 SF개, 느리게 시작해서 느리게 끝나는 노래가 SS개 있다.
중복 없이 다음 조건을 만족하면서 뽑을 수 있는 최대 곡 수를 구하시오.

1. 빠르게 시작하는 노래는 반드시 빠르게 끝나는 노래의 바로 다음에 와야 한다.
2. 느리게 시작하는 노래는 반드시 느리게 끝나는 노래의 바로 다음에 와야 한다.
3. 빠르게 시작하는 노래가 한 곡이라도 있다면, 맨 처음 곡은 빠르게 시작하는 곡이어야 한다.

정답 코드 및 설명

경우의 수를 나누어서 생각하면 쉽다.

1. 빠르게 시작하는 노래가 한 곡도 없는 경우
   • FF = FS = 0인 경우이다.
   • 느리게 시작해서 느리게 끝나는 노래는 개수에 상관없이 붙일 수 있다.
   • 느리게 시작해서 빠르게 끝나는 노래가 있다면, 맨 끝에 최대 한 개만 올 수 있다.
   • 최대 갯수는 SS + min(SF, 1)개이다.
2. 빠르게 시작하는 노래는 있지만, 빠르게 시작해서 느리게 끝나는 노래가 한 곡도 없는 경우
   • FF는 0이 아니지만, FS = 0인 경우이다.
   • 빠르게 시작해서 빠르게 끝나는 노래만을 계속해서 붙일 수 있다.
   • 최대 갯수는 FF개이다.
3. 그 외의 경우
   • 시작하는 템포와 끝나는 템포가 같은 노래는 얼마든지 아무렇게나 붙일 수 있다.
   • 시작하는 템포와 끝나는 템포가 다른 노래를 최대 몇 개까지 뽑을 수 있는지 생각해보자.
   • 빠른 템포 - 느린 템포 - 빠른 템포 - 느린 템포 … 순으로 번갈아가면서 진행되어야 한다.
   • 3-1) FS > SF
     • 빠른 템포 - 느린 템포 - … - 빠른 템포 순으로 진행되는 것이 최대로 뽑는 경우이다.
     • 느린 템포 -> 빠른 템포로의 변환은 SF번 이루어진다.
     • 빠른 템포 -> 느린 템포로의 변환은 SF + 1번 이루어진다.
     • 최대 곡의 갯수는 FF + SS + 2 * SF + 1개
   • 3-2) SF ≥ FS
     • 빠른 템포 - 느린 템포 - … - 느린 템포 순으로 진행되는 것이 최대로 뽑는 경우이다.
     • 빠른 템포 -> 느린 템포로의 변환은 FS번 이루어진다.
     • 느린 템포 -> 빠른 템포로의 변환은 FS번 이루어진다.
     • 최대 곡의 갯수는 FF + SS + 2 * FS개

이를 코드로 구현하면 아래와 같다.

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

public class BOJ1581 {
    int ff, fs, sf, ss;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ff = Integer.parseInt(st.nextToken());
        fs = Integer.parseInt(st.nextToken());
        sf = Integer.parseInt(st.nextToken());
        ss = Integer.parseInt(st.nextToken());
    }

    int ans() {
        if (ff == 0 && fs == 0) return ss + Math.min(sf, 1);
        if (fs == 0) return ff;
        int changeTempo;
        if (fs > sf) changeTempo = 2 * sf + 1;
        else changeTempo = 2 * fs;
        return ff + ss + changeTempo;
    }

    void solution() throws IOException {
        input();
        System.out.println(ans());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1581().solution();
    }
}