인프런 커뮤니티 질문&답변
작성한 질문수
7-M 질문 있습니다.
해결된 질문
작성
·
44
0
안녕하세요.
강의도 듣고 제 나름대로 구현을 해보았는데, 테스트 케이스는 다 통과하는데, 어째선지 내부 테스트 케이스를 통과를 못하는것 같습니다.
열심히 봤는데 이유를 모르겠네요... 부탁드립니다.
http://boj.kr/c1ff73d9fcf3471d9459e8a7fa24e793
감사합니다.
답변 2
0
안녕하세요 비스킷님 ㅎㅎ
처음에는 틀린부분을 찾으려고 했지만 그런게 좀 쉽지가 않아서
제가 하는 방법을 썼습니다. 저는 제가 틀릴 때 코드 전체를 다듬으면서 다시 짜는데요.
비스킷님 코드 기반으로 다시 짜봤습니다.
#include <bits/stdc++.h>
using namespace std;
struct Tree {
int y, x, age;
};
int n, m, k;
const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
void SpringSummer(vector<Tree>& trees, vector<vector<int>>& cur_energy) {
vector<Tree> alive;
vector<Tree> dead;
sort(trees.begin(), trees.end(), [](const Tree& a, const Tree& b) {
return a.age < b.age;
});
for (auto& tree : trees) {
if (cur_energy[tree.y][tree.x] >= tree.age) {
cur_energy[tree.y][tree.x] -= tree.age;
tree.age += 1;
alive.push_back(tree);
} else {
dead.push_back(tree);
}
}
for (const auto& tree : dead) {
cur_energy[tree.y][tree.x] += tree.age / 2;
}
trees = move(alive);
}
void Fall(vector<Tree>& trees) {
vector<Tree> new_trees;
for (const auto& tree : trees) {
if (tree.age % 5 == 0) {
for (int i = 0; i < 8; ++i) {
int ny = tree.y + dy[i];
int nx = tree.x + dx[i];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
new_trees.push_back({ ny, nx, 1 });
}
}
}
}
trees.insert(trees.end(), new_trees.begin(), new_trees.end());
}
void Winter(vector<vector<int>>& cur_energy, const vector<vector<int>>& charge) {
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
cur_energy[y][x] += charge[y][x];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
vector<vector<int>> cur_energy(n, vector<int>(n, 5));
vector<vector<int>> charge_amount(n, vector<int>(n));
vector<Tree> trees;
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
cin >> charge_amount[y][x];
}
}
for (int i = 0; i < m; ++i) {
int x, y, age;
cin >> y >> x >> age;
trees.push_back({ y - 1, x - 1, age });
}
for (int i = 0; i < k; ++i) {
SpringSummer(trees, cur_energy);
Fall(trees);
Winter(cur_energy, charge_amount);
}
cout << trees.size() << "\n";
return 0;
}
처음에 정리한 코드입니다.
깔끔하죠?
그러나 이 코드는 시간초과입니다.
그래서
deque 등을 사용해서 효율적으로 다시 만들어봤습니다.
#include <bits/stdc++.h>
using namespace std;
struct Tree {
int age;
};
int n, m, k;
const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
void SpringSummer(vector<vector<deque<Tree>>>& trees, vector<vector<int>>& cur_energy) {
vector<vector<int>> add_energy(n, vector<int>(n, 0));
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
deque<Tree>& cell = trees[y][x];
deque<Tree> new_trees;
while (!cell.empty()) {
Tree tree = cell.front();
cell.pop_front();
if (cur_energy[y][x] >= tree.age) {
cur_energy[y][x] -= tree.age;
tree.age += 1;
new_trees.push_back(tree);
} else {
add_energy[y][x] += tree.age / 2;
}
}
cell = move(new_trees);
}
}
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
cur_energy[y][x] += add_energy[y][x];
}
}
}
void Fall(vector<vector<deque<Tree>>>& trees) {
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
deque<Tree>& cell = trees[y][x];
for (const auto& tree : cell) {
if (tree.age % 5 == 0) {
for (int d = 0; d < 8; ++d) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
trees[ny][nx].push_front({1});
}
}
}
}
}
}
}
void Winter(vector<vector<int>>& cur_energy, const vector<vector<int>>& charge) {
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
cur_energy[y][x] += charge[y][x];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
vector<vector<int>> cur_energy(n, vector<int>(n, 5));
vector<vector<int>> charge_amount(n, vector<int>(n));
vector<vector<deque<Tree>>> trees(n, vector<deque<Tree>>(n));
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
cin >> charge_amount[y][x];
}
}
for (int i = 0; i < m; ++i) {
int x, y, age;
cin >> y >> x >> age;
trees[y - 1][x - 1].push_back({age});
}
for (int i = 0; i < k; ++i) {
SpringSummer(trees, cur_energy);
Fall(trees);
Winter(cur_energy, charge_amount);
}
int result = 0;
for (int y = 0; y < n; ++y) {
for (int x = 0; x < n; ++x) {
result += trees[y][x].size();
}
}
cout << result << "\n";
return 0;
}
참고 부탁드립니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 비스킷님.
테스트 케이스는 통과했지만 내부 테스트 케이스에서 실패하는 경우는 상당히 흔한 문제 중 하나로, 아래 몇 가지 방법을 통해 이유를 찾아볼 수 있습니다:
경계 조건 확인: 종종 코드가 입력 데이터의 경계 조건을 제대로 처리하지 못할 때 이런 문제가 발생합니다. 예를 들어 최소값 또는 최대값 근처, 혹은 빈 입력에 대해 처리를 빠트릴 수 있습니다.
정확한 제한 확인: 백준의 문제 조건을 다시 한 번 확인해 보세요. 특히, 제한 사항이나 문제에서 요구하는 출력 형식을 놓치지 않았는지 점검하십시오.
자료형 오버플로우: 연산 결과가 자료형의 범위를 초과할 수 있는지 확인해보세요. 특히 int를 사용했을 때 이러한 문제가 발생할 수 있으며,
long long을 사용하는 것이 좋을 수 있습니다.논리 오류: 알고리즘의 흐름이 잘못되었거나 일부 로직이 더 효율적으로 개선될 수 있는지도 점검해보세요. 논리적인 오류가 발생할 가능성을 염두에 두고 디버깅해보세요.
유사한 문제 해결에 관한 기존 질문을 참고하시면 추가적인 통찰을 얻으실 수 있습니다. 다음은 관련된 질문 URL입니다:
- 7-M 시간초과 질문입니다. - 이 질문에서는 알고리즘의 비효율성으로 인한 시간초과 문제를 다루고 있습니다.
위의 답변들을 검토해 보시고 코드의 경계 조건, 제한, 자료형의 적절성을 점검하세요. 이해가 가지 않는 부분이 있으시면, 이어서 질문해 주시기 바랍니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.