Hyun's_Devlog

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

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

정답 코드

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

그리디 문제다. 

풀이

소와 닭의 이동시간을 비교해서 조건이 맞는 경우를 세는 문제다. 단, 여기서 중요한 점은 소의 이동가능시간이다. 해당 부분의 정렬 조건에 대해 생각하는 데에 오랜 시간이 걸렸다. 

닭 i가 소 A와 소 B 두 마리 모두 데려다줄 수 있는 경우, 둘 중 이동 가능 시간의 범위가 더 좁은 경우를 우선적으로 선택해야 선택받지 못한 소를 다음 순번의 닭이 데려다줄 가능성이 더 높아지게 된다. 즉 닭의 시간을 오름차순 정렬, 소의 이동시간이 짧은 순서 & 움직이기 시작한 시간이 오름차순으로 정렬이 되어야 한다는 이야기다.

소의 움직임이 완료된 시간을 기준으로 오름차순, 움직임이 완료된 시간이 같다면 움직이기 시작한 시간 기준으로 오름차순으로 정렬한 뒤, 오름차순으로 정렬된 닭의 시간을 기준으로 데려갈 수 있는 소들을 탐색하여 접근하였다.

정답 코드

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

기본적인 그리디 문제다. 오래전에 오답판정을 받고서 이번에 다시 풀어보았다. 사소한 부분을 놓친 거라 원인을 알고 나서 허탈했다.

풀이

현실에서의 시간은 24시간이지만, 문제에서 주어지는 시간의 최댓값은 1,000,000이다. 오답의 원인도 해당 부분을 꼼꼼히 보지 않아서 생긴 것이다. 정답으로 출력할 time변수를 시작시간의 최댓값 1,000,000으로 설정한다.

입력되는 일들을 마감시간을 기준으로 내림차순으로 정렬한 뒤, 시작시간이 마감시간보다 뒤에 있다면 시작시간을 (마감시간 - 작업시간)으로 변경한다.

만일 시작시간이 마감시간보다 앞에 있다면 작업시간만큼 앞당긴다.(빼준다.) 마지막으로 정답을 출력할 때, 시작시간이 음수라면, -1을 출력한다.

정답 코드

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

그리디 문제다. 숫자가 아닌 문자열로 접근해서 풀었다. 숫자로 접근하게 된다면 최대 범위가 0 ~ 2,000,000,000 이므로 분명 시간 초과가 일어날 것이다. 따라서 8이 나올 수 있는가에 대한 조건만 생각해서 접근해야 한다.

우선 자릿수의 변동이 일어나면 8이 나올 수 없다. 즉 L과 R의 자릿수를 먼저 체크해야 하고, 이후 자릿수가 같다면 어느 자리까지 제한하였는지를 확인해야 한다. 각 자릿수의 숫자가 같을 경우에만 8의 개수를 세고 각 자릿수가 달라지는 시점이 온다면 해당 숫자는 8이 아닌 수로 바꿀 수 있다는 뜻으로 접근하면 된다.

풀이

자릿수가 다르다면 8이 없는 구간이 생길 수밖에 없으니 0을 출력하면 된다.

자릿수가 같다면 가장 큰 자릿수부터 숫자를 비교하여 8의 개수를 세면 되는데, 서로의 숫자가 다르다면 더 이상 숫자를 셀 필요 없다.

정답 코드