백준 2873 C++ (롤러코스터)

한참 헤맸던 문제였다...

그리디 알고리즘 문제라고 했는데 어디가 그리디인지는 잘 모르겠다..ㅎ

체스판 문제유형에 익숙해지도록 하자.

시간 제한	메모리 제한	정답률
1초	256MB	28.658%

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

핵심

r이 홀수이거나 c가 홀수일 때는 그냥 모든 곳을 지나가면 되기 때문에 쉽다.
둘 다 짝수일 경우, 기쁨이 가장 적은 곳을 피해 지나가면 된다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


using namespace std;

int r, c, minn, minn_c, minn_r;
int happy[1001][1001];

void r_odd(){
    for(int i=0;i<r/2;i++){
        for(int j=1;j<c;j++){
            cout << 'R';
        }
        
        cout << 'D';
        
        for(int j=1;j<c;j++){
            cout << 'L';
        }
        
        cout << 'D';
    }
    
    for(int j=1;j<c;j++){
        cout << 'R';
    }
    
    cout << '\n';
}

void c_odd(){
    for(int i=0;i<c/2;i++){
        for(int j=1;j<r;j++){
            cout << 'D';
        }
        
        cout << 'R';
        
        for(int j=1;j<r;j++){
            cout << 'U';
        }
        
        cout << 'R';
    }
    
    for(int j=1;j<r;j++){
        cout << 'D';
    }
    
    cout << '\n';
}


void even(){
    string ans = "";
    string ans2 = "";
    
    int x1 = 0;
    int x2 = r-1;
    int y1 = 0;
    int y2 = c-1;
    
    while(x1/2 < minn_r/2){
        for(int j=0;j<c-1;j++){
            ans.push_back('R');
        }
        ans.push_back('D');
        for(int j=0;j<c-1;j++){
            ans.push_back('L');
        }
        ans.push_back('D');
        
        x1 += 2;
    }
    
    while(x2/2 > minn_r/2){
        for(int j=0;j<c-1;j++){
            ans2.push_back('R');
        }
        ans2.push_back('D');
        for(int j=0;j<c-1;j++){
            ans2.push_back('L');
        }
        ans2.push_back('D');
        
        x2 -= 2;
    }
    
    
    
    while(y1/2 < minn_c/2){
        ans.push_back('D');
        ans.push_back('R');
        ans.push_back('U');
        ans.push_back('R');
        y1 += 2;
    }
    
    while(y2/2 > minn_c/2){
        ans2.push_back('D');
        ans2.push_back('R');
        ans2.push_back('U');
        ans2.push_back('R');
        y2 -= 2;
    }
    
    if(minn_c == y1){
        ans.push_back('R');
        ans.push_back('D');
    }
    else{
        ans.push_back('D');
        ans.push_back('R');
    }
    
    reverse(ans2.begin(), ans2.end());
    
    ans += ans2;
    
    cout << ans << '\n';
}



int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    minn = 1000000;
    
    cin >> r >> c;
    
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> happy[i][j];
            
            if((i+j)%2==1 && happy[i][j] < minn){
                minn_r = i;
                minn_c = j;
                minn = happy[i][j];
            }
        }
    }
    
    //cout << "min : " << minn << '\n';
    
    if(r%2 == 1) r_odd();
    else if(c%2 == 1) c_odd();
    else even();
    
	return 0;
}