2096번 - 내려가기

2024-02-14

#C++#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
n줄에 0이상 9이하의 숫자가 세개씩 적혀있다.

•
첫줄에서 가장 마지막줄까지 이동하면서 세가지 숫자 중 하나를 고른다.

•
마지막 줄에서 얻을 수 있는 최대 점수, 최소 점수를 구해라

문제 풀이

이 문제는 dp로 풀 수 있겠다고 생각했다.

초기 코드

C++

#include <iostream>
#include <vector>

using namespace std;

int min_arr[100001][3], max_arr[10001][3], input[10001][3];
int dir[3][2] = {-1, 0, -1, -1, -1, 1};
int n;

bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= 3)
        return false;
    return true;
}

void dp_min() { //최소 점수 구하기
    int x = 1, y, tx, ty;
    for (; x < n; x++) { //줄 번호
        for (y = 0; y < 3; y++) { //줄 당 숫자
						//현재 칸에 값을 초기화 해준다
            min_arr[x][y] = input[x][y] + min_arr[x + dir[0][0]][y + dir[0][1]]; 
            for (int i = 1; i < 3; i++) { //위의 다른 칸에서 내려왔을 때 경우 확인하기
                tx = x + dir[i][0];
                ty = y + dir[i][1];
                if (!check(tx, ty))
                    continue;
                if (min_arr[x][y] > input[x][y] + min_arr[tx][ty])
                    min_arr[x][y] = input[x][y] + min_arr[tx][ty];
            }
        }
    }
}

void dp_max() { //최대 점수 구하기
    int x = 1, y, tx, ty;
    for (; x < n; x++) {
        for (y = 0; y < 3; y++) {
            max_arr[x][y] = input[x][y] + max_arr[x + dir[0][0]][y + dir[0][1]];
            for (int i = 1; i < 3; i++) {
                tx = x + dir[i][0];
                ty = y + dir[i][1];
                if (!check(tx, ty))
                    continue;
                if (max_arr[x][y] < input[x][y] + max_arr[tx][ty]) {
                    max_arr[x][y] = input[x][y] + max_arr[tx][ty];
                }
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input[i][0] >> input[i][1] >> input[i][2];
        if (i == 0) { //첫번째줄 초기화 해주기
            for (int j = 0; j < 3; j++) {
                min_arr[0][j] = input[i][j];
                max_arr[0][j] = input[i][j];
            }
        }
    }
    dp_min();
    dp_max();
    int min = min_arr[n - 1][0], max = max_arr[n - 1][0];
    for (int i = 1; i < 3; i++) { //최대, 최소 점수 구하기
        if (min > min_arr[n - 1][i])
            min = min_arr[n - 1][i];
        if (max < max_arr[n - 1][i])
            max = max_arr[n - 1][i];
    }
    cout << max << " " << min;
}

위 코드가 좀 더럽긴해도 맞다고 생각했는데

이상하게 3%에서 틀렸다고 뜬다.

이유는 모르겠다.

그래서 다른 사람의 풀이를 조금 참고했다.

최종 코드

C++

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input[0] >> input[1] >> input[2];
        for (int j = 0; j < 3; j++) {
            max_arr[i][j] = input[j];
            min_arr[i][j] = input[j];
        }
        if (i == 0) {
            continue;
        } //무작정 큰값 대입해주기
        max_arr[i][0] = max(max_arr[i - 1][0], max_arr[i - 1][1]) + input[0];
        max_arr[i][1] = max(max_arr[i - 1][0], max(max_arr[i - 1][1], max_arr[i - 1][2])) + input[1];
        max_arr[i][2] = max(max_arr[i - 1][1], max_arr[i - 1][2]) + input[2];
				//무작정 작은값 대입해주기
        min_arr[i][0] = min(min_arr[i - 1][0], min_arr[i - 1][1]) + input[0];
        min_arr[i][1] = min(min_arr[i - 1][0], min(min_arr[i - 1][1], min_arr[i - 1][2])) + input[1];
        min_arr[i][2] = min(min_arr[i - 1][1], min_arr[i - 1][2]) + input[2];
    }

    int min = min_arr[n - 1][0], max = max_arr[n - 1][0];
    for (int i = 1; i < 3; i++) {
        if (min > min_arr[n - 1][i])
            min = min_arr[n - 1][i];
        if (max < max_arr[n - 1][i])
            max = max_arr[n - 1][i];
    }
    cout << max << " " << min;
}

생각보다 너무 간단하고 무지성으로 풀 수 있었던 문제…