문제
격자 지도에서 각 열을 위에서 아래로 시추할 때, 암반(
H)은 비용 3, 모래(S)는 비용 1이 들고 석유(X)를 만나면 총 비용을 출력한다. 석유가 없으면N을 출력한다.
풀이
각 열을 위에서 아래로 훑으면서 비용을 누적한다. X를 만나면 누적 비용을 출력하고, 열이 끝날 때까지 X를 못 만나면 N을 출력한다.
코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void solve(int t) {
int h, w;
if (!(cin >> h >> w)) return;
vector<string> map(h);
for (int i = 0; i < h; ++i) {
cin >> map[i];
}
cout << "Data Set " << t << ":" << endl;
for (int j = 0; j < w; ++j) {
int totalCost = 0;
bool found = false;
for (int i = 0; i < h; ++i) {
if (map[i][j] == 'X') {
found = true;
break;
} else if (map[i][j] == 'H') {
totalCost += 3;
} else if (map[i][j] == 'S') {
totalCost += 1;
}
}
if (found) cout << totalCost;
else cout << 'N';
if (j < w - 1) cout << " ";
}
cout << endl << endl;
}
int main() {
int k;
if (!(cin >> k)) return 0;
for (int i = 1; i <= k; ++i) {
solve(i);
}
return 0;
}복잡도
- 시간: O(h * w)
- 공간: O(h * w)