백준 10709 - 기상캐스터 ( C++ )

 

안녕하세요 besforyou입니다

 

백준 문제 10709번 문제 풀이를 설명하겠습니다

---

문제 풀이

 

c가 나온 지점으로부터 오른쪽으로 얼마나 떨어져 있는지를 알아내어 출력하는 문제입니다.

 

이 문제에 dp 알고리즘을 적용하면 O(H*W) 시간안에 풀어낼 수 있습니다.

 

1. 구름의 위치 입력값을 받을 2차원 배열 cloud와 정답을 기록할 2차원 배열 ans를 생성합니다.

 

2. 2차원 배열 ans의 모든 원소값은 -1로 초기화합니다. (memset 이용)

 

3. 2차원 배열 cloud에 모든 입력값을 저장합니다.

 

4. for문을 이용하여 cloud의 모든 원소를 순차적으로 참조하는데,

 

1. 해당 cloud 좌표에 c가 있는 경우 : 0

2. c가 참조되지 않았지만 이전 원소가 -1이 아닌 경우(c가 이전에 이미 읽힌 경우) : 이전 원소 값 + 1

 

를 출력합니다.

 

이때 정답으로 출력하는 값을 또 다른 배열 ans에 기록하여 이후의 계산에 활용합니다.

 

코드 

#include <iostream>
#include <cstring>
using namespace std;
// 1
char cloud[101][101];
int ans[101][101];
 
int main (void) {
   
    int H,W;
    cin >> H >> W;
    // 2
    memset(ans, -1, sizeof(ans));
    // 3
    for (int i = 1; i <= H ; i++) {
        for (int j = 1; j <= W ; j++ )
            cin >> cloud[i][j];
    }
    // 4
    for (int i = 1; i <= H ; i++) {
        for (int j = 1; j <= W ; j++ ) {
            if ( cloud[i][j] == 'c' ) { //4 - 1
                ans[i][j] = 0;
            }
            else if ( cloud[i][j] == '.' && ans[i][j-1] != -1 ) { //4 - 2
                ans[i][j] = ( ans[i][j-1] + 1 );
            }
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}