[백준 - 1253] 좋다
문제: https://www.acmicpc.net/problem/1253
문제는 굉장히 간단하다.
그런데 정말 예기치 못한 반례가 많이나와서 많이 틀렸다.
처음 짤 땐 그냥 두 수를 더해보고 멀티셋 count 만큼 답을 증가시키고, 멀티셋에서 해당 수를 빼 주었다. 그랬더니 다음과 같은 반례가 있었다.
0 3
0이 등장하면 생기는 반례를 전혀 고려하지 못했다...
그래서 골라준 두 수중 하나라도 0 이라면, 멀티셋.count가 2 이상인 경우만 카운트 해줬다. 그랬더니 다음과 같은 반례가 있었다
0 0
... 그래서 두 수가 모두 0인 경우도 따로 예외처리를 해주었다.
코포에서 이런문제 나오면 시스템 채점에서 나락갈듯... 문제풀 때 신중히 풀어야겠다.
[백준 - 15824] 너 봄에는 캡사이신이 맛있단다
문제: https://www.acmicpc.net/problem/15824
일단 정렬을 하고 시작하자.
최소가 i, 최대가 j 의 위치인 경우의 수는 2^(j-i-1)개 이다.
i와 j의 모든 경우를 탐색하려면 O(N^2)만큼 걸리므로 안될 것이다.
그런데 i와 j사이의 거리가 같은 것들은 한번에 계산 할 수가 있다.
예를들어 원소가 5개이고, 거리가 3인 조합을 생각해보자
2와 8, 5와 10 이렇게 짝을 지어볼 수 있다.
오른 쪽에 있는 숫자들은 +가 되고 왼쪽은 -가 될 것이다.
그러므로 {(오른쪽 총합)-(왼쪽 총합)} * 2^(거리-1) 만큼 스코빌 지수가 증가 할 것이다.
누적합으로 구현 할 수도 있을 것 같고 나는 투포인터로 한칸씩 움직이면서 계산했다.
시간 복잡도는 정렬 때문에 O(NlogN)이다.
