[코드포스] Round #811 (Div. 3)

안녕하세요 aim_higher 입니다.

코드포스 Round #811 (Div. 3) 코드리뷰 및 업솔빙입니다.

---

A. Everyone Loves to Sleep

https://codeforces.com/contest/1714/problem/A

• Implementation(구현)

 

H시 M분에 Vlad라는 친구가 잠을 잡니다.

하지만, n개의 알람들이 설정이 되어있어 Vlad의 알람이 울리는 순간 수면은 종료됩니다.

이때, Vlad가 얼마나 잠을 잘 수 있는지를 출력하시면 됩니다.

 

이때, 유의하셔야 할 점이 있는데요

잠든 시간 이전에 설정 되어있어서 듣지 못했던 알람들은

다음 날에도 같은 시간에 울린다는 점입니다.

---

알람의 시와 분을 {h*60+m}형태로 입력받고,

위에 설명한 것처럼 잠든 시간 이전에 설정된 알람들은 24h를 추가해줬습니다.

받은 입력값들을 오름차순으로 sort해주어 가장 작은 값을 얻을 수 있습니다.

그렇다면, "가장 작은 값 - 잠든 시간"이 정답이 되겠네요.

 

물론, 제가 시간을 임의대로 변환하고 "연산"을 진행했기 때문에

m이 60이상인 경우에는 h로 변환해주는 작업을 거쳐주었습니다.

이러면 아무런 문제없이 정답을 출력할 수 있습니다.

---

B. Remove Prefix

https://codeforces.com/contest/1714/problem/B

• Greedy(그리디)

Polycarp은 n개의 길이로 되어있는 정수로 이루어진 순열이 있습니다.

각 원소의 index를 i, 수열의 각 정소 원소를 ai라고 할 때

i를 정의역, ai를 치역이라고 생각한다면 일대일 함수를 이루어야 Polycarp이 행복해진다고 합니다.

즉, 서로 다른 index값에서 해당 index에 대응되는 원소값 ai이 같은 경우가 나와서는 안된다는 겁니다.

 

Polycarp이 위와 같이 행복해지는 수열을 만들기 위해서

수열의 가장 왼쪽 원소를 제거하는 연산을 진행할 수 있습니다.

최종적으로, 몇번의 최소한의 연산을 거쳐야 Polycarp이 행복해질 수 있는지를 출력하면 됩니다.

---

이 문제는 왼쪽에서 삭제하는 연산이라 왼쪽에 집중하여 실제로 제거하려고 하시면 안되고,

보자마자 오른쪽부터 순회하며 원소를 memo하여 중복되는 숫자가 있는 시점에서 멈추시면 됩니다.

 

예제 1를 예로 들자면,

[3  1  4  3]에서 오른쪽 부터 순회해 보겠습니다.

3 (3 : 1개)

4 (3 : 1개 / 4 : 1개)

1 (1 : 1개 / 3 : 1개 / 4 :1개)

3 (3: 2개??) → STOP

 

이러한 접근 방식이 결국 왼쪽에서 제거하는 효과를 내게됩니다.

그렇다면 정답은 쉽게 나옵니다. 저는 c++ map을 사용했습니다.

---

C. Minimum Varied Number

https://codeforces.com/contest/1714/problem/C

• Greedy(그리디)

1부터 45사이의 수를 하나 던져줍니다. (1에서 9까지의 합이 45라 바로 느낌오죠?)

1부터 9까지의 숫자 중에서 서로 다른 숫자를 중복없이 추출하여 합해서 주어진 수를 만들면 됩니다.

이때 필요한 최소한의 숫자의 개수를 출력해야 합니다.

---

솔직히 말하면 이 문제는 A번 문제 수준으로 너무 쉽습니다.

그냥 9부터 1까지 순회하면서 쓸 수 있는 건 최대한으로 쓰면 됩니다.

사용한 숫자의 개수를 더해서 출력하면 정답입니다(...)

---

D. Color with Occurrences

https://codeforces.com/contest/1714/problem/D

• Greedy(그리디)

로직은 바로 짰는데 구현이 너무 킹받아요.

안해