[Softeer]Pipelined

레벨 3 문제 하나씩 풀다가.. 

푼 사람은 적은데 정답률은 높아서 시도해봤다.

https://softeer.ai/practice/9496

그런데... 아무리 문제를 봐도 문제가 무슨 내용인지 이해가 안간다..

연습문제 톡을 확인해보니 어떤분이 백준 문제를 보면 이해가 간다고 링크를 걸어놨다.(감사합니다ㅠㅠ)

백준문제 보니까 문제가 이해가 간다..

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

 

 

백준에서 먼저 풀어보고 소프티어 답을 제출했는데,

정답을 받기까지 삽질을 좀 했다...

 

1. 첫번째 삽질.

그러니까,,생산 단계 프로세스가 주어지는데, 구간이 겹치지 않도록 할당했을때 최소 걸리는 시간을 구하는데,

그래서 최초에 할당된 상태로 시작하는가?

최초에 무에서 시작하는가? 이것도 헷갈림;;

 

예제문제를 보고 최초 한개는 할당 된 상태로 시작하는걸로 간주했다.

 

1/s1 구간을 할당받아서 시작한다고 했을때, 지금 시작하는 1/s2가 이전에 돌렸던 1/s1 보다 값이 작으면 시작할수 있다고 간주했다.(이게 무슨말?)

1. 주어진 단계 프로세스를 오름차순으로 정렬.

2. 각 단계 프로세스마다 이전 단계 프로세스를 검사해서, 이전 단계보다 그 뒤에 있으면 슬롯을 옮겨주었다.

→(이때 2/si 와 2/s2 를 비교하기 위해서 챗gpt 한테 분수의 대소 구분하는걸 물어봤다.. 실수로 변환하여 대소구분하는건 한계가 있을것같아서. 친절한 챗gpt로 분수 대소 구별하는 간단한 지식을 얻었다.)

 

결론은 시간초과..

 

2. 두번째 시도.

첫번째 1%에서 시간초과라니ㅠ

두번째로 좀 멍청한 시도를 해봤다.

오름차순을 제외하고, 각 단계 프로세스를 검사할때 이미 [0,1) 구간이 끝난건 뛰어넘어줬다.

2%에서 시간초과..

 

3. 새로운 세번째 시도.

애초에 이 방법이 틀렸다는걸 인지했다.

어떻게 풀지?? 생각하면서 보다가..

각 단계프로세스가 큰것부터 1/5씩 이동하고, 그 다음은 1/7 이동하고, 그다음은 1/8.. 이런씩으로 이동하면

애초에 제일 첫번째로 시작했던 프로세스와 두번쨰부터 시작하는 프로세스는 서로 겹칠 일이 없다.

왜냐? 작은 숫자부터 1/n 씩 이동하면 그 다음에 이동하는 슬롯은 이전 슬롯보다 크기가 작을수밖에 없어서

앞 슬롯을 절대 따라잡을 수 없다..

 

코드가 엄청 간결해졌다.

n이 200000 이라서 배열로 선언하지 않고, 제일 마지막 숫자에 (n-1)값을 더해줬다.

틀림.

 

4. 네번쨰 시도.

왜틀렸지? 하면서 보다가

아.. 바보같은 실수를 했다.

제일 첫번째 시도할땐 오름차순 정렬도 했었는데,, 그걸 그새 까먹었다.

단계별 프로세스 슬롯이 주어질때 오름차순으로 주어진다는 말은 없었는데!!

결론은, max 값에 n-1을 더한 값을 제출했다.

 

정답!!

알고보면 매우 간단했는데, 괜히 복잡하게 생각했다.

 

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int ans = n-1;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 1;
        for(int i=0; i<n; i++){
            int num = Integer.parseInt(st.nextToken());
            max = Math.max(num, max);
        }
        ans += max;

        bw.write(String.valueOf(ans));
        bw.close();
    }

}