안녕하세요, 삼색 그래프 문제를 풀다가 궁금한 점이 두 가지 생겨서 질문 올립니다.

1. 실패한 코드의 원인 분석

우선 문제의 힌트 태그를 보기 전까지는 올바른 해결책을 떠올리기 힘들어서 여러 가지 방법으로 접근했었고, 그러한 과정에서 예제로 시뮬레이션을 돌려보며 패턴을 찾을 수 밖에 없었습니다. 제가 관찰한 것은 다음과 같습니다.

(1) 분말스프의 사용 횟수 X가 주어질 때 모든 횟수를 사용하는게 당연히 이득이다.

(2) 빨간색에 스프를 K회 사용하면 (1)에 의해 파란색에는 자동으로 X - K 회의 스푼을 사용하게 된다.

(3) 위의 (2) 과정을 f(K) 라는 함수로 하면, f(0) 의 값부터 f(X)의 값에 이르기 까지의 함수 개형은 두개의 직선이 교차하는 형태가 된다. /\

(4) 함수 개형으로부터 최댓값이 등장하는 두 직선의 교점 p를 구하기 위해 f(0), f(1) 를 구해서 왼쪽 직선의 방정식을 구하고, f(X - 1), f(X) 를 구해서 오른쪽 직선의 방정식을 구한다.

(5) 두 직선의 방정식으로부터 구한 교점의 함숫값이 곧 최댓값이 된다.

(6) 예외처리 : f(0) == f(1) == f(X - 1) == f(X) 일 경우, 즉 분말스프의 영향이 없는 경우 그냥 f(0) 이 정답이다.

하지만 이렇게 작성한 코드는 25% 가량에서 WA를 맞았고, 적당한 반례를 떠올리지 못한 채 다른 방법으로 접근해서 문제를 풀어냈습니다.
그러나 함수 개형을 생각해보면, 꽤나 그럴듯한 풀이라고 생각하는데 어떻게 반례가 생길 수 있는지가 궁금합니다.

2. 코드의 시간 분석

이 후 일반적인 풀이 방법을 통해 AC를 받은 두 코드의 시간이 조금 크게 차이가 납니다. 채점번호 39656868 와 39657275 는 완전히 동일한 코드임에도 불구하고 약 2000ms의 차이가 발생했습니다. 백준 저지 시스템에 대한 이해도는 부족하지만, 그럼에도 몇가지 추론을 해보자면

(1) 채점 데이터가 매번 테스트마다 랜덤으로 생성된다.

(2) 채점 서버 상태에 따라 결과가 달라질 수 있으며 저 정도 결과 차이는 감수해야 한다.

(3) 작성한 코드가 경우에 따라 최적화가 이루어질 가능성이 존재한다.

이 중 어느 부분의 가능성이 가장 높은지, 조언해주신다면 정말 감사하겠습니다.