2816 - 디지털 티비

https://www.acmicpc.net/problem/2816

처음에 재귀로 다 돌려봤는데, 역시 시간초과였다.

노트에 채널 목록을 적어서 화살표로 직접 이동시켜봤는데, 문제를 다시 보니 "최소의 이동"이라는 말은 없었다 (!!)

첫 번째 채널부터 화살표를 아래로 계속 이동시키면서(1번 버튼) KBS1 을 찾는다. 찾은 후에는 KBS1을 첫 번째 채널까지 올린다.(4번) KBS2도 1번으로 찾아서 두 번째 채널까지 4번 버튼으로 올리면 된다.

방법의 최대 길이가 500이니 위아래로 화살표가 왕복을 2번 해도 400번이면 충분하다.

그리디는 생각하기 너무 어렵다.

#include <bits/stdc++.h>
using namespace std;

typedef long long int lld;
typedef unsigned long long llu;

#define KBS1 70030
#define KBS2 116686

llu hashValue(char *s){
    llu val=0, cr=1;
    for(int i=0; s[i]; ++i, cr*=36){
        if(s[i]>='0' && s[i]<='9') val += (s[i]-'0')*cr;
        else val += (s[i]-'A')*cr;
    }
    return val;
}

int main(){
    int i, n;
    scanf("%d ", &n);
    llu channel[101];
    for(i=0; i<n; ++i){
        char s[11];
        scanf("%s", s);
        channel[i] = hashValue(s);
    }
    
    int len = 0, ptr = 0;
    char trace[501]={};
    while(channel[ptr] != KBS1){
        trace[len++] = '1';
        ptr += 1;
    }
    while(ptr != 0){
        trace[len++] = '4';
        swap(channel[ptr], channel[ptr-1]);
        ptr -= 1;
    }
    while(channel[ptr] != KBS2){
        trace[len++] = '1';
        ptr += 1;
    }
    while(ptr != 1){
        trace[len++] = '4';
        swap(channel[ptr], channel[ptr-1]);
        ptr -= 1;
    }
    puts(trace);
    
    return 0;
}