[ Baekjoon - 10/20 ] - 1581번: 락스타 락동호

• 문제 링크 : https://www.acmicpc.net/problem/1581

1581번: 락스타 락동호

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 빠른 시작-빠른 끝(FF),  빠른 시작-느린 끝(FS),  느린 시작-빠른 끝(SF),  느린 시작-느린 끝(SS)
       (0≤FF, FS, SF, SS≤1,000)
     • [_F]는 무조건 [F_]앞에 와야하고, [_S]는 무조건 [S_]앞에 와야한다
     • [F_]가 하나라도 있다면 첫곡은 [F_]형태여야한다.
     • 위 조건을 만족할때, 최대 몇곡까지 실을 수 있는지 출력하는 문제
   • 이해
     • 문제이해는 어렵지 않았고, 끄적여보며 규칙을 발견해야 풀수있다고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제이해가 어렵지 않아서 생략
3. 문제를 어떻게 해결할 것인가

   • 

   • 조건을 적어보았고, 케이스별로 형태를 분석해보았다.
     1. F로 시작하는 형태가 없을 때
        • SF나 SS로 시작하여야하고, 조건 1,2에 따라 SF이면 F로 시작하는 곡, FS이면 S로 시작하는 곡이 와야한다.
        • 하지만 FS는 F로 시작하는 형태이기때문에 올수없으므로 SS로 시작하는 형태만 가능하다
        • SS로 시작하면 뒤에 SS와 가장 끝에 SF만 올 수 있다!
     2. F로 시작하는 형태가 있을 때
        • FS나 FF로 시작하여야하고, 조건에 따라 FS이면 S로 시작하는 곡, FF이면 F로 시작하는 곡이 와야한다.
        • F로 시작하는 형태가 존재한다는 것은 FF와 FS가 둘다 있거나 둘중 하나만 있거나임.
        • FF로 시작할때 뒤에 F로 시작하는 형태가 와야하는데,
          만약, FF만 있고, FS가 없는 경우라면 FF만 올 수 있으므로 FF의 개수만으로 최대개수가 결정지어진다.
        • 그게 아닌 나머지의 경우에서는,
          FF나 SS는 계속 쭉 이어 붙일 수 있으므로, SF와 FS가 개수를 결정짓는다.
        • F로 시작할때는 FF+...+FF+FS+SS+....+SS+SF 같은 형태이거나, FS+SS+...+SS+SF+FF+...+FF 같은 형태이다.
        • FS가 SF보다 많다면, SF가 개수를 결정짓고, 반대의 경우라면 FS가 개수를 결정짓는다.
4. 위 계획을 검증
   • 규칙을 찾기위해 케이스별로 나눠 따져본 것이므로 이미 검증이라 볼 수 있다. 
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int ff, fs, sf, ss;
        
            public static void main(String[] args) 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());
        
                System.out.println(ans());
            }
        
            private static int ans() {
                if (ff == 0 && fs == 0)
                    return ss + Math.min(sf, 1);
                if (fs == 0)
                    return ff;
        
                if (fs > sf)
                    return ff + ss + 2 * sf + 1;
                else
                    return ff + ss + 2 * fs;
            }
        }

   2. Python 3

      • import sys
        input = sys.stdin.readline
        
        def ans():
            if ff == 0 and fs == 0:
                return ss + min(sf, 1)
            if fs == 0:
                return ff
        
            if fs > sf:
                return ff + ss + 2 * sf + 1
            else:
                return ff + ss + 2 * fs
        
        
        if __name__ == '__main__':
            ff, fs, sf, ss = map(int, input().split())
            print(ans())

 

 

• 결과