[JAVA] BOJ(백준) - 락스타 락동호 - 1581

문제내용

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

1581번: 락스타 락동호

한국이 낳은 세계적인 락스타 락동호는 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보다 크다.

출력

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

---

문제 풀이

알고리즘 연습 사이트에서 완전 탐색으로 분류 돼있길래 반복문을 돌려야하는 줄 알았는데,,, 풀다보니 반복문은 커녕 그냥 조건문만 잘해주면 풀수 있는 문제였다.

 

크게 분리할수 있는 조건은 2가지다.

1. 빠른곡으로 시작하는 곡이 없다.

2. 빠른곡으로 시작하는 곡이 있다.

 

1번의 경우 최대한 수록할수 있는 곡의 수.

• SF SS 곡이 존재한다 -> SS를 전부 앨범에 담고, 마지막에 SF를 하나 담아준다. -> SS개수 + 1
• SS 곡만 존재한다 -> SS개수
• SF 곡만 존재한다 -> 1

 

2번의 경우 최대한 수록할수 있는 곡의 수.

• FS 곡이 없다 -> FF개수
• FF FS 곡이 존재한다 -> FF를 먼저 전부 담는다 -> FS 하나 담는다 -> SS를 전부 담는다 -> FS와 SF 나머지를 개수에 따라 담아준다. -> FF개수 + FS 하나 + SS 개수 + SF개수 + FS개수 + (만약 FS<SF이면 마지막에 +1)
• FF 곡이 없다 -> FF FS 곡이 존재할때의 과정에서 FF개수가 드가는것만 빼주면된다. -> FS 하나 + SS 개수 + SF개수 + FS개수 + (만약 FS<SF이면 마지막에 +1)

 

이렇게 6가지의 경우를 분기문으로 살펴보면 바로 풀린다.

 

---

코드

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

public class Main {
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[4];
		for(int i=0; i<4; i++) 
			arr[i] = Integer.parseInt(st.nextToken());
		
		int ans=0;
		
		if(arr[0]==0 && arr[1]==0 && arr[2]!=0 && arr[3]!=0) ans = arr[3]+1; //빠른곡으로 시작하는거 없을때 경우 1.
		else if(arr[0]==0 && arr[1]==0 && arr[2]==0 && arr[3]!=0) ans = arr[3]; //빠른곡으로 시작하는거 없을때 경우 2.
		else if(arr[0]==0 && arr[1]==0 && arr[2]!=0 && arr[3]==0) ans = 1; //빠른곡으로 시작하는거 없을때 경우 3.
		else {//빠른거로 시작하는거 있을때.
			if(arr[0]!=0 && arr[1]==0) ans += arr[0]; //FS 곡이 없다.
			else if(arr[0]!=0 && arr[1]!=0) { //FF FS 가 존재할때.
				ans += arr[0]+1;//FF개수 + FS 하나
				arr[1]--;
				ans += arr[3]; //현재까지 마지막곡은 FS -> SS곡을 모두 담는다.
				if(arr[1]>=arr[2]) ans += (arr[2]*2); //FS가 SF보다 크거나 같다면 SF를 다쓸수 있음.
				else if(arr[1]<arr[2]) ans += (arr[1]*2)+1; //SF가 FS보다 크다면 FS를 다쓰고 마지막에 SF곡 을 담을수 있음.
			}
			else if(arr[0]==0 && arr[1]!=0) { //FF가 없을때.
				ans = 1;//FS로 시작
				arr[1]--;
				ans += arr[3];
				if(arr[1]>=arr[2]) ans += (arr[2]*2);
				else if(arr[1]<arr[2]) ans += (arr[1]*2)+1;
			}
		}
		System.out.println(ans);
	}
}

---

마치며

완전탐색인줄 알았지만 아닌 문제,, 경우의수를 다 살피니까 어떻게 보면 완전탐색이라 할 수 있겠지만 평소에 풀던 문제와는 다른느낌이다.