인프런 커뮤니티 질문&답변
작성한 질문수
백준11505, 교재 73번
작성
·
196
0
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
static vector<long> tree;
static int n, m, k,mod = 1000000007;
void tree_set(int a);
void change_val(int index, long val);
long gugan(int s, int e);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
int q = n;
int l = 0;
while (q != 0) {
q = q / 2;
l++;
}
int tree_size = int(pow(2, l+1));
int left_index = pow(2, l);
tree.resize(tree_size);
fill(tree.begin(), tree.end(), 1);
for (int i = left_index; i < n+left_index; i++) {
cin >> tree[i];
}
tree_set(tree_size-1);
for (int i = 0; i < m + k; i++) {
long a, s, e;
cin >> a >> s >> e;
if (a == 1) {
change_val(s + left_index - 1, e);
}
else if (a == 2) {
long start = s + left_index - 1;
long end = e + left_index - 1;
long result = gugan(start, end);
cout<<result<<'\n';
}
}
}
long gugan(int s, int e) {
long part_sum = 1;
while (s <= e) {
if (s % 2 == 1) {
part_sum *= tree[s]%mod;
}
if (e % 2 == 0) {
part_sum *= tree[e]%mod;
}
s = (s + 1) / 2;
e = (e - 1) / 2;
}
return part_sum;
}
void change_val(int index, long val) {
tree[index] = val;
while (index > 1) {
index = index / 2;
tree[index] = tree[index*2]%mod*tree[index*2+1]%mod;
}
}
void tree_set(int a) {
while (a != 1) {
tree[a / 2] *= tree[a]%mod;
a--;
}
}
위의 방법으로 코드를짜서 제출했더니 출력초과가 발생합니다. 왜 이런오류가 발생하는지 모르겠습니다..
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
님께서 공유해주신 코드는 세그먼트 트리를 사용하여 구간 곱을 계산하는 방식으로 보입니다.
‘출력 초과’ 라는 오류는 범위를 벗어난 과도한 출력이 발생했을 때 나타나는 오류로, 일반적인 상황에서는 코드 내에서 불필요한 출력이 발생하지 않았는지 확인해야 합니다. 그러나 여기에서는 코드 자체에서 불필요한 출력이 없어 보이며, 근본적인 원인보다는 문제의 조건이나 제출 환경에 대해서 고려해볼 필요가 있습니다.
문제의 조건이나 세그먼트 트리의 구현 방식에 오류가 있을 수도 있기 때문에 다음 점들을 확인해 보시는 것이 좋을 것 같습니다:
1. 세그먼트 트리의 크기와 초기화가 올바르게 이루어졌는지 확인해보세요.
2. 구간 곱을 계산하는 ‘gugan’ 함수에서 모듈로 연산을 적절하게 사용했는지 다시 검토해보세요.
3. ‘change_val’ 함수에서 세그먼트 트리를 업데이트 하는 로직이 제대로 동작하는지 점검해보세요.
4. 입출력에 대한 처리가 문제와 일치하는지 검토하세요. 예를 들어, 문제에서 요구하는 출력 포맷과 다르게 출력하고 있지는 않은지 확인해보세요.
질문하신 문제의 정확한 해결을 위해서는 조금 더 많은 정보가 필요합니다. 올바른 입력 범위, 문제의 조건 등에 대해 문제가 발생하지 않도록 주의를 기울여 서브밋 해보시길 바랍니다.