대경권 대학생 프로그래밍 경진대회 3번 with 프로그래머스

 

 

요약하면 문제는 입력된 명령어대로 움직였을 때, 지나온 길의 수를 찾는것이다.  입력이 매우 작으므로 그냥 나올 수 있는 모든 길을 저장하는 2차원 배열(footprints)을 선언해 메모이제이션 했다.

 

 

코드

 

#include <string>
#include <algorithm>
#include <memory.h>
using namespace std;


# -5~5의 범위를 가지는 2차원 좌표를 정수 하나로 변환 해주는 함수.
int flatten(int y, int x){
    y += 5;
    x += 5;
    return y*11+x;
}

int footprints[122][122];
int solution(string dirs)
{
    int answer = 0;
    int now_y = 0;
    int now_x = 0;

    for (auto i=dirs.begin(); i!=dirs.end(); i++){
        int prev_y = now_y;
        int prev_x = now_x;

		switch (*i){
            case 'U':
                now_y += 1;
                break;
            case 'D':
                now_y -= 1;
                break;
            case 'R':
                now_x += 1;
                break;
            case 'L':
                now_x -= 1;
                break;
        }

        if(now_y < -5) now_y = -5;
        if(now_y > 5) now_y = 5;
        if(now_x < -5) now_x =-5;
        if(now_x > 5) now_x = 5;

        int flat_prev = flatten(prev_y, prev_x);
        int flat_now = flatten(now_y, now_x);

        if( (flat_prev != flat_now)
           && (footprints[flat_prev][flat_now] == 0)){
            footprints[flat_prev][flat_now] = 1;
            footprints[flat_now][flat_prev] = 1;
            answer += 1;
        }
    }
    return answer;
}