18790번 - N의 배수 (1)
알고리즘은 다음과 같습니다.
최종목표는 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%에서 틀렸는데 왜 틀렸는지 모르겠습니다 ㅠㅠ<지금까지 시도한 반례들>
41 1 3 3 0 2 2 ->0 3 3 220 1 1 -> 1 120 1 0-> 0 041 2 3 0 1 2 3-> 0 3 3 210-> 05 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 110 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
5
1 2 3 4 0 1 2 3 41 2 3 4 0 이 나와야 하는데
-1을 출력하네요
참고로 스페셜 저지니까 다른 답이 있을수도 있고, 출력 순서는 상관없습니다 하지만 -1은 아닙니다.
어라...? 저는 0 4 1 4 1 이 나옵니다
다시 한번 해보니 위에 올린 TC로는 0 4 1 4 1이 나오네요.
제가 착각했네요 죄송합니다.
N = 500인 경우에 출력이 이상하네요
TC 하나 올려봅니다.
500.txt
로 생성한 TC입니다.
(int)n으로 출력하신 이유가 char형이라서 그렇게 하신 것 같은데
char 범위를 넘는 수들은 음수로 출력 되는 것 같네요..
그러므로 11번 라인을 아래와 같이 수정하시면 25%에서 시간초과를 받게됩니다.
오마갓... 감사합니다!! ㅠㅠㅠㅠㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
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