역대 최악의 성적이다.
그도 그럴것이, 낮에 백준에서 다이아2짜리 문제 푼다고 너무 고생해서 머리가 너무 아픈 상태였는데,어쩔 수 없이 진행했다..
근데, 그럼에도 불구하고 결과를 보면 blue유지가 가능한 점수다. 확실히 요즘 blue는 예전 cyan인듯 하다.
영어 해석이 안 되서 너무 오래걸렸다.
index가 짝수면 'z'에 가깝게, 홀수면 'a'에 가깝게 바꿔주면 된다.
직관적으로 공격력이 낮은 녀석부터 패줘야 최적의 답이다.
한 번 제출했는데 틀리길래 공격력 순이 아니라 한 녀석과 전투하는 동안 감소하는 총 체력순으로 패줘야하나? 싶어서 그렇게 접근해봤지만 fail.
나중에 보니 int overflow때문이었다.
집중력 흐트러지니 진짜 별의 별 실수를 다 하는구나 느낀 문제다.
1~n의 숫자가 distinct하게 무작위로 들어있는 배열이 있을 때, 양 옆의 두 값보다 낮은 값의 index중 하나를 찾아내야 하는 문제다. 찾을 땐 query를 보내서 서버로 부터 온 응답으로 찾아야하는 interactive 문제다.
solution은 binary search인데, mid에 쿼리 날리고 mid - 1에 쿼리 날리고 mid + 1에 쿼리 날려서 조건을 만족하면 mid가 answer고, 아니라면 arr[mid - 1]값과 arr[mid + 1]의 값 중 작은 값이 있는 쪽으로 분할하여 탐색하면 된다.
백준 중간 이 문제를 최근에 풀어서 보자마자 solution이 생각나서 바로 풀었다.
다만, 역시.. 컨디션이 많이 안 좋은걸 느낀게 1번 틀렸는데, base case처리 후 return을 안 해줘서 틀렸다... 에휴..
D1. Painting the Array I , D2. Painting the Array II
코포에서 dp가 나오네... 오랜만이다 하고 dp로 접근했는데 택도 없었다. greedy다.
dp로 안 풀리지는 않는데 O($n^2$)의 solution밖에 없다. O($n$)으로 만들려고 별의 별 짓을 다 해봤는데, 참조적 투명성이 보장되지 않아서 O($n^2$)밖에 안 된다.
문제를 각 원소를 두 배열에 넣으면서 조건을 만족하는 최대 result를 구하는 문제로 보면,
원소 $a_i$를 둘 중 어느 배열에 넣을지 판단하는 기준은 아래와 같다.
$a_i$와 두 배열의 마지막 값을 비교하여,
(1)만약 두 마지막 값 모두 $a_i$와 같다면, 그냥 아무데나 넣어준다.
(2)만약 둘 중 하나의 값이 $a_i$와 다르다면, 그 배열에 넣어준다.
(3)만약 둘 다 다르다면, 두 마지막 값 $A_l, B_l$에 대해 다음에 들어올 값들 중 $A_l$과 같은 값이 먼저 들어오면 $A$배열에 넣어주고, 반대라면 $B$배열에 넣어준다.
(1), (2)조건은 자명한 것이고, (3)조건이 직관적으로 알아차리기 조금 알쏭달쏭한데, 두 배열의 마지막 값과 같은 값이 오는 시간(index)가 계속 튕겨 나가듯이 update된다고 생각하면 된다. 튕겨나갈 index는 같은데, 그럼 둘 중 어느 녀석을 튕겨내줄까? 생각해보면 가장 먼저 같은 값이 올 녀석을 튕겨내줘야 한다는 것을 직관적으로 파악 가능하다.
D1.은 위 조건으로 풀리고, D2.는 위 조건을 반대로 수행해주면 풀린다.
