1-N 문제 질문입니다. (+ 채점오류)

Question

#include using namespace std; #define ll long long ll A, B, C, R; stack st; int main() { cin >> A >> B >> C; while (B != 1) { A %= C; if (B % 2 == 1) { st.push(A); } A = (A * A) % C; B = B / 2; } A %= C; while (!st.empty()) { ll i = st.top(); st.pop(); A = (A*i) % C; } cout << A; return 0; } 안녕하세요. 큰돌님. 질문이 있어서 글을 남기게 되었습니다. 테스트 #1인 [10 11 12]에 대해서만 시간 초과 오류가 발생합니다. (로컬에서 시도했을때는 정상 출력되는 것을 확인했습니다.) 하지만, 왜 시간 초과가 발생하는 지 이유를 알지 못하겠습니다. 위 코드 방식대로라면 반복문이 3번에 끝나게 된다고 생각하는데, 무엇이 잘못된 부분인지 알려주시면 감사할 것 같습니다. 감사합니다. +++) 9/14, 18:49 방금 확인해봤는데, 정답 코드 그대로 제출해도 똑같이 시간초과가 납니다.! (채점서버도 최신으로 업데이트 해봤습니다.!)

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. 이승헌님. 제시하신 입력 10 11 12 에서는 B 가 다음과 같이 변하므로 반복문이 정상적으로 종료됩니다. B = 11 → 5 → 2 → 1 따라서 해당 입력만으로는 무한 반복이 발생하지 않습니다. 다만 현재 코드는 while (B != 1) 조건을 사용하고 있어, 만약 B 가 0 으로 들어오면 다음과 같이 계속 0 에 머무르게 됩니다. B = 0 B / 2 = 0 즉, B 가 0이 될 가능성까지 고려한다면 다음처럼 B > 0 을 조건으로 사용하는 것이 더 안전합니다. ll result = 1; while (B > 0) { A %= C; if (B % 2 == 1) { result = (result * A) % C; } A = (A * A) % C; B /= 2; } cout << result; 또한 현재 코드처럼 홀수인 지수에서 사용할 A 를 스택에 저장하는 방식도 원리상 동작할 수 있지만, 결과를 별도의 result 변수에 바로 곱하는 방식이 더 직관적이고 오류 가능성이 적습니다. 거듭제곱을 분할 정복으로 계산할 때는 홀수인 경우 A 를 한 번 더 곱하고, 매 단계마다 % C 를 적용해야 합니다. 이와 관련된 기존 답변은 아래 게시글에서 확인하실 수 있습니다. 1-N 1629 홀수 일 때의 처리가 이해가 되지 않습니다. 현재 입력 10 11 12 만으로는 반복문이 3회 실행되므로, 실제 채점에서 시간 초과가 발생한다면 제출한 코드와 질문에 첨부한 코드가 동일한지, 그리고 채점 데이터에서 B = 0 이 입력될 수 있는지 확인해 보시는 것이 좋습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.