백준 1636번 한번 열면 멈출 수 없어

문제 설명

이번 문제는 프링글스마다 중독 스트레스 범위가 주어지고 원숭이가 프링글스를 먹을 때 해당 프링글스의 중독 스트레스 범위 내에서 중독 스트레스를 스스로 조절할 수 있습니다. 하지만, 중독 스트레스를 조절할 때마다 예상 수명이 1년씩 줄어들게 됩니다.

원숭이가 N개의 프링글스를 열어서 모든 프링글스를 무조건 먹게될 경우, 프링글스를 한 통씩 먹으면서 원숭이가 중독스트레스를 조절할 때, 줄어드는 예상 수명을 최소화하는 프로그램을 작성하는 문제입니다.

 

문제 풀이

아이디어

이전 프링글스와의 중독 스트레스 범위 비교 경우의 수와 스트레스 조절 최소화

이전 프링글스의 중독 스트레스 범위를 a1~b1(노란색), 현재 프링글스의 중독 스트레스 범위룰 a2~b2(초록색)라고 할 때,

 

1. b1 < a2인 경우

b1 < a2

이전에 조절된 스트레스에서 a2로 스트레스 조절하는 것이 최소로 조절하는 방법입니다.

 

2. a1 <= a2<=b1 and b1 <= b2 인 경우

a1 <= a2<=b1 and b1 <= b2

이전에 조절된 스트레스 지점이 a1~(a2-1)라면 a2로 이동,

a2~b1라면 이동하지 않는 것이 최소로 조절하는 방법입니다.

 

3. a1 <= a2 and b2 <= b1 인 경우

a1 <= a2 and b2 <= b1

이전에 조절된 스트레스 지점이 a1~(a2-1)이거나 (b2+1)~b1이라면 각각, a2, b2로 이동하고,

a2~b2라면 이동하지 않는 것이 최소로 조절하는 방법입니다.

 

4. a2 < a1 and b1 < b2 인 경우

a2 < a1 and b1 < b2

이전에 조절된 스트레스 지점에서 이동하지 않는 것이 최소로 조절하는 방법입니다.

 

5. a2 <= a1 <= b2 and b2 <= b1인 경우

a2 <= a1 <= b2 and b2 <= b1

이전에 조절된 스트레스 지점이 (b2+1)~b1라면 b2로 이동,

a1~b2라면 이동하지 않는 것이 최소로 조절하는 방법입니다.

 

6. b2 < a1인 경우

b2 < a1

이전에 조절된 스트레스에서 b2로 스트레스 조절하는 것이 최소로 조절하는 방법입니다.

 

 

풀이

첫 스트레스 조절 위치 정하기

만약 스트레스 조절 범위가 겹쳐 있다가 겹쳐 있지 않은 범위가 나타났을 때를 생각해보겠습니다.

예시 이미지

다음과 같이 5개의 프링글스의 스트레스 조절 범위가 나타나있다고 가정해보겠습니다.

1번부터 4번 프링글스까지 스트레스 범위 중 s~e가 겹치게 됩니다.

그리고 5번째 프링글스의 조절범위와 비교하면 e<s5로 위 아이디어의 경우의 수1과 같습니다.

그렇다면 4번 프링글스에서 5번 프링글스로 넘어갈 때 줄어든 예상 수명을 최소로 하는 방법은 s~e범위의 수 중 e에서 s5로 이동하는 경우입니다. (s에서 e 사이의 수 중에서 s5과 가장 가까운 수는 e이므로 예상 수명을 최소로 줄일 수 있습니다.)

그러므로 1번부터 4번까지의 조절된 스트레스는 모두 e가 되고 5번은 s5이 됩니다.

 

위와 같이 겹쳐진 스트레스 조절 범위에서 벗어나는 조절 범위가 나타났을 때 그 벗어난 범위에서 가장 가까운 수가 첫 번째 프링글스부터 조절된 스트레스가 됩니다.

 

조절된 스트레스 구하기

아이디어의 경우의 수를 토대로 조절된 첫 스트레스 조절 위치 다음의 스트레스를 구하면 됩니다.

 

 

해결

첫 스트레스의 조절 위치를 구하는 범위를 혼동하여 조금 맞왜틀 했던 문제입니다...

 

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

1636번: 한번 열면 멈출 수 없어

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1636.py