백준 28426 더하기와 나누기

문제

28426번: 더하기와 나누기 (acmicpc.net)

28426번: 더하기와 나누기

 

 

풀이

다른말로하면, A의 원소는 sum(A)의 약수가 아니란 것이다.

해 구성하기가 사실 운빨이 중요하기도 하다 보긴하는데, 나같은경우는 기본형을 만들고 거기서 값을 변형/추가하며 정답을 도출한다.

홀수는 짝수의 약수가 될 수 있지만, 짝수는 홀수의 약수가 될 수 없다.

따라서 A를  2부터 2 + 2(N-1)의 짝수들로 우선 채워준다. A의 원소는 모두짝수이고 sum(A)를 홀수로 만들면 A의 원소는 sum(A)의 약수가 없을 것이다.(기본형: 2이상의 짝수가 채워진 수열)

따라서 A에서 적당한 값을 하나 삭제하고 임의의 홀수를 넣어준다.

원래문제에서 약수가 하나 있어야하므로 새로 넣어주는 홀수는 새로운 sum(A)의 약수가 돼야한다.

편의상, 2 + 2(N-1) (가장 큰 짝수)를 삭제한다. (난 그랬다. 다른수를 삭제해도 될 것이다.)

그 다음 2이상 2+2(N-2)이하 짝수들의 합을 구한다. 이를 s하자.

새로운 홀수를 k라하자. (s + k) % k = 0가 되면된다.

문제에서 조건을 만족하는 수열은 항상 존재한다고 했다.

k를 3이상 10^6미만 홀수들을 다 넣어주면서 (s+k)%k가 0가 되면 답을 도출해낸다.

for i in range(1, N + 1):
    ans.append(2 * i)
ans.pop()
ref = sum(ans)
for i in range(3, 10 ** 6, 2):
    val = ref + i
    if val % i == 0:
        ans.append(i)
        break

근데 여기서 찝찝함을 느꼈다. 증명을 해보자.

 

증명

풀이에서 가장 큰 짝수를 삭제했으므로 홀수를 추가하기전의 sum(A) = N(N-1)일 것이다. 등차수열 합 공식에 대입해본 결괴이다.(초항이 2이고 공차가 2) 이는 N에 상관없이 홀수 * 짝수 형식이다.

N(N-1) + k = x * k (k는 홀수,x는 정수)가 돼야한다. N(N-1) = (x-1)k가 돼야한다.

좌변은 홀수*짝수이다. 우변은 홀수*(x-1)이다. x-1은 짝수가 돼야한다. 적당한 k와 적당한x가 존재한다.

 

 

특수한 경우

많은 문제에서 N이 작다면 규칙에 안맞는 경우가 있다.

(여기선 N=1과 N=2라면 규칙에 안맞음을 알 수 있다.)

이건 그냥 구해주면된다. 브루트포싱을 쓰든 뭘하든...

케이스처리를 해줘야한다.