인프런 커뮤니티 질문&답변
작성한 질문수
5-V 질문드립니다.
작성
·
50
0
안녕하세요 큰돌님 항상 강의 잘 듣고 있습니다.
제가 문제를 풀때는 누적합 배열을 따로 만들 생각은 하지 못했지만 그 외에는 큰돌님 해설과 크게 다르지 않은 로직을 짰습니다.
각각의 구간합에 따라서 나오는 경우의 수를 저장해서 그 값을 저장해서 전체 경우의 수를 구했는데 틀렸습니다.
혼자 꽤 많이 고민해봐도 안 풀려서 도움 요청드립니다...
답변 2
0
안녕하세요 예찬님 ㅎㅎ
for 문 - innerloop 자체가 좀 모호해서 그런 것 같습니다.
for (int r = l; temp == 0 || r != (l - 1 + n) % n; r = (r + 1) % n) {
이부분을 이런식으로 바꿔보시겠어요?
for (int step = 0; step < n; ++step) {
int r = (l + step) % n;
다른 부분은 다 괜찮은 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 문예찬님.
누적합 문제 관련해서 고민하고 계시는 것 같습니다. 누적합은 배열의 각 인덱스까지의 합을 저장해서, 특정 구간의 합을 빠르게 계산할 수 있게 해주는 방법입니다. 이는 특히 부분 합을 계속해서 계산해야 하는 문제에서 유용하며, 불필요한 계산을 줄여 성능을 향상시킵니다.
제공하신 링크를 통해 Devyond에 대한 질문을 이해했는데, 비슷한 문제가 해결된 사례들을 공유드리겠습니다:
1주차 개념 9 누적합 질문있습니다 - 누적합을 적용한 문제 해결 사례입니다. 이 질문에서도 배열을 활용한 부분 합 계산의 중요성을 다루고 있습니다.
1-H 2559번 질문있습니다! - 문제 제출 후 오답 처리 상황에 대한 논의입니다. 이 질문에서 특정 인덱스로 인한 연산 문제를 다루고 있습니다.
질문해주신 부분에 대한 직접적 해결책을 찾는 데 초점을 맞춰, 기존 누적합과 각 구간합 문제를 해결할 때의 주의사항을 염두에 두시기 바랍니다. 구현 과정에서 구간의 시작, 끝 인덱스를 잘못 설정하여 맞지 않는 경우의 수가 발생할 수 있습니다.
또한, 각각의 누적합 계산에서 인덱스 오프셋이 필요할 수 있으니 코드 내부의 for-loop나 if 조건문을 다시 한 번 검토해 보시면 좋겠습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 감사합니다..!! 큰돌님 답변을 보고 그대로 해봤지만 틀리게 나와서 나름 고민을 해봤습니다.
http://boj.kr/ba44723257c5472386105686add6b046
원형 순열에서 각 구간합에 대해서 그 값이 몇번 나오는 지에 대한 로직에서 고려했어야 하는 '전체 구간합' 중복 제거를 하는 과정에서 실수가 있었습니다.
큰돌님께 질문드리기 전에 제 코드에서 원래 해당 for문은
for (int r = l; temp == 0 || r != l; r = (r + 1) % n) { ... }이었습니다. r 값이 l과 같아지기 직전까지 구간합을 구해나가는 건데 r이 l과 같아지기 직전은 전체 구간합을 계산하는 것이고 전체구간합을 계산할 때 그 구간의 출발점이 어디였는지에 따라 (l값에 따라) 따로 세고 있습니다. 전체의 합은 한가지 경우인데 중복으로 세고 있었던 것이죠. 큰돌님 해설코드의 10번째줄,if(interval == n) break;처럼 전체구간합을 세는 데에 있어서 중복을 제거해주는 부분이 없었습니다.그래서 제 for문을 한 칸 덜 가도록 해서 피자의 사이즈보다 하나 작은 크기의 구간합까지만 세고 전체구간합은 따로 구해주기로 했습니다. 그래서
r != l의 조건을r != (l - 1 + n) % n로 고쳤습니다. 이 부분이 큰돌님이 지적해주신 부분인데 제가 생각했을 때는 이 부분은 문제가 없었습니다.전체 구간합을 따로 생각해주기 위해서 입력을 받을 때 전체구간합을 계산하고 이 값이 손님이 원하는 크기(sum)와 같다면 cnt++ 해줬습니다. (큰돌님 코드에서의 ret)
하지만 전체구간합에 대해 중복을 제거하기 위해 원래 루프안에 있던 로직을 밖으로 빼낸 것이기 때문에 전체구간합에 대해 처리할 때 루프안의 로직처럼 그대로 그 값이 sum과 같다면 cnt++해주고 (이건 했음) sum보다 작다면 map[temp]++를 해줘야 했습니다.(이 부분을 빼먹음) 그래서 다음과 같이 고쳐서 맞았습니다.
http://boj.kr/9d860e2a5dc6472c9c8642d76d8a0051
제가 큰돌님이 답변해주시기 전에 이걸 못알아차려서 이렇게 말씀드립니다.
항상 좋은 강의 감사합니다.