museum114   4년 전

알고리즘은 다음과 같습니다.

최종목표는 N개를 골라서 그 합을 N으로 모듈러 계산한 결과가 0인 것!

즉 N개의 합이 N의 배수이면 됩니다.

이 때 가능한 나머지는 0~N-1입니다.

우선 dp에 나머지들을 저장합니다. 

혹시 N개 이상 들어온 데이터가 있으면 그 데이터가 정답이므로 출력합니다.
N개 이상 들어온 데이터 합을 N으로 나눈 나머지는 무조건 0이기 때문입니다.

N이 1이면 Input data를 그대로 출력합니다. 1은 모든 수를 잘 나눌 수 있습니다.

그 다음이 제가 고안한 알고리즘인데요.

N개를 골라야 한다는 건 N-1개와 1개를 고르는 일입니다. 모듈러 연산은 분배법칙을 적용할 수 있으니

제가 N-1개의 수를 골라서, N으로 나눴을 때 나머지가 i가 되는 합을 만들고 N-i을 값으로 지니는 수를 고르면

둘을 더해서 N으로 나눴을 때 나머지가 0입니다. 예를 들어 N이 5라고 했을 때 4개의 수를 골라서 5로 나눈 나머지가 3이 되도록 하고 2(5-3)을 값으로 지니는 수를 고르면 둘을 더해서 ( 2 + 3) 5로 나누면 나머지가 0입니다.

이 i를 Answer string에 붙입니다. 

이제 3개의 수를 골라서 그 합의 나머지가 어떤 수 J가 되도록하고 이 J와 더해서 N으로 나눴을 때 나머지가 3가 되도록 하는 k를 찾습니다. 이 k도 정답 스트링에 넣습니다.

이런 과정을 N-1번 반복하는 식의 알고리즘입니다...

4%에서 틀렸는데 왜 틀렸는지 모르겠습니다 ㅠㅠ

<지금까지 시도한 반례들>

4

1 1 3 3 0 2 2
->0 3 3 2

2
0 1 1
-> 1 1

2
0 1 0
-> 0 0

4
1 2 3 0 1 2 3
-> 0 3 3 2

1
0
-> 0

5
1 2 3 4 0 1 2 3 4
-> 0 4 1 4 1

10
1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 4 4 5 6 7 8 9
-> 1 4 4 1 3 3 1 1 1 1

10
0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 6 7 8 9
->0 0 0 0 0 0 4 3 2 1

10 

9 9 9 9 9 9 9 9 9 8 8 8 8 8 8 8 8 7 7 7 

-> 7 9 9 8 7 8 8 8 8 8

201812106   4년 전

5

1 2 3 4 0 1 2 3 4

1 2 3 4 0 이 나와야 하는데 

-1을 출력하네요

201812106   4년 전

참고로 스페셜 저지니까 다른 답이 있을수도 있고, 출력 순서는 상관없습니다 하지만 -1은 아닙니다.

museum114   4년 전

어라...? 저는 0 4 1 4 1 이 나옵니다

201812106   4년 전

다시 한번 해보니 위에 올린 TC로는 0 4 1 4 1이 나오네요.

제가 착각했네요 죄송합니다.

N = 500인 경우에 출력이 이상하네요

TC 하나 올려봅니다.


500.txt



201812106   4년 전

로 생성한 TC입니다.

201812106   4년 전

(int)n으로 출력하신 이유가 char형이라서  그렇게 하신 것 같은데


char 범위를 넘는 수들은 음수로 출력 되는 것 같네요..

201812106   4년 전

그러므로 11번 라인을 아래와 같이 수정하시면 25%에서 시간초과를 받게됩니다.

museum114   4년 전

오마갓... 감사합니다!! ㅠㅠㅠㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.