[백준] 1563번 - 개근상

https://www.acmicpc.net/problem/1563

1563번: 개근상

문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

---

여러 가지 경우의 수가 있다. N 이 1000이기에 재귀함수로 풀기에는 시간이 부족하므로 dp로 풀 생각을 해야 한다.

dp [현재 날짜][연속된 결석일 수][지각 횟수]로 설정하여 마지막 dp [N][][] 일의 합을 출력하면 된다.

dp[i+1][0][0] = dp[i][0][0] + dp[i][1][0] + dp[i][2][0] // 이 사람들이  i + 1일에 출석
dp[i+1][0][1] = dp[i][0][0] + dp[i][1][0] + dp[i][2][0] // 이 사람들이 i + 1일에 지각
                 + dp[i][0][1] + dp[i][1][1] + dp[i][2][1] // 이 사람들이 i + 1일에 출석
dp[i+1][1][0] = dp[i][0][0];
dp[i+1][1][1] = dp[i][0][1];
dp[i+1][2][0] = dp[i][1][0];
dp[i+1][2][1] = dp[i][1][1];

이때 주의해야 할 점은 1,000,000으로 나눈 나머지 이므로 덧셈 연산이 있을 때마다 나머지를 구해준다.

 

 

---

맨 처음에 dp로 점화식을 구한 후 코드 작성을 완료하고 제출하기 전 다시 한번 살폈다. 이때 1,000,000으로 나눈 나머지를 구하라고 해서 1000을 입력했을 때 나눈 것과 안나눈 것을 비교했다. 나누지 않았을 때 349666861가 나와 마지막 합에만 나눗셈을 주었다. 그러자 틀렸습니다가 나왔다. 그래서 long long으로 바꾸고도 제출했지만 틀렸다. 그리고 반복문 안에 덧셈이 있을 때마다 나머지 연산을 넣고 실패하고 마지막에 출력에서 한번 더 나머지 연산을 주니 성공했다. 오버 플로우가 일어나서 음수를 넘어서 또 양수가 되는 것을 반복했던 것이었다. 맨 처음 1000을 입력했을 때 숫자를 보고 저 숫자인데 왜 나머지 연산을 하라고 했지?라는 생각을 가졌다. N을 시험을 여러 번 했으면 괜찮았을 것 같은데 아쉽다. 나머지를 출력하는 문제에서 항상 여러 번 틀리는 것 같다. 나머지 연산 문제는 여러 값이 합쳐지는 부분이 있으면 나누고 봐야하는 것 같다!