2873 - 롤러코스터

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

홀수x짝수, 짝수x홀수, 홀수x홀수 크기에 대해서는 모든 경로를 방문하여 가장 오른쪽 아래 칸으로 갈 수 있다.

짝수x짝수 크기는 1칸 빼고 나머지는 다 방문해서 도착할 수 있는데, (홀수, 짝수) 또는 (짝수, 홀수)에 위치한 칸을 들리지 못한다. 빼는 1칸은 가장 작은 기쁨이 있는 칸을 선택하면 될 것이다.

여기까지는 어떻게 생각해냈는데, 경로를 어떻게 만들어야할지 몰라서 한참 고민하다 결국 솔루션을 참고해버렸다.

경로를 크게 3부분으로 나눈다.

가운데 지그재그로 제외할 1칸을 피해서 이동하는 것 때문이다. 지그재그로 2줄만 어떻게 해결하면 되므로, 그 전행까지는 R...RDL...LD 로 이동하고, 이후의 행부터는 DL...LDR...R 로 이동하면 된다.

#include <cstdio>
using namespace std;

int H, W;
int a[1000][1000];

void repeat(char ch, int repeated){while(repeated-->0)putchar(ch);}

int main(){
    scanf("%d %d", &H, &W);
    
    for(int i=0; i<H; ++i){
        for(int j=0; j<W; ++j){
            scanf("%d", &a[i][j]);
        }
    }
    
    if( H%2 ){
        repeat('R', W-1);
        for(int i=0; i<H-1; i+=2){
            repeat('D', 1); repeat('L', W-1);
            repeat('D', 1); repeat('R', W-1);
        }
    } else if( W%2 ){
        repeat('D', H-1);
        for(int i=0; i<W-1; i+=2){
            repeat('R', 1); repeat('U', H-1);
            repeat('R', 1); repeat('D', H-1);
        }
    } else {
        // finding minimum cell
        int x=0, y=1;
        for(int i=0; i<H; ++i){
            for(int j=0; j<W; ++j){
                if((i+j)%2 && a[y][x] > a[i][j]){
                    y = i, x = j;
                }
            }
        }
    
        int h=0, w=0;
        // top
        for(; h+1 < y; h += 2){
            repeat('R', W-1); repeat('D', 1);
            repeat('L', W-1); repeat('D', 1);
        }
        
        // middle
        int ny = h^1;
        for(w=0; w < W-1; ++w){
            if( ny != y || w != x ){
                repeat( ny%2 ? 'D':'U', 1);
                ny ^= 1;
            }
            repeat('R', 1);
        }
        if( ny%2 ) repeat('D', 1);
        
        // bottom
        h = (h/2*2) + 2;
        for(; h < H; h += 2){
            repeat('D', 1); repeat('L', W-1);
            repeat('D', 1); repeat('R', W-1);
        }
    }
    
    return 0;
}

1541 - 잃어버린 괄호

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

음수 부호(-)가 나오는 순간부터 모든 수가 음수라고 생각하면 된다. a+b-(c+...+z) 가 되기 때문.

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

int main() {
    char s[101];
    scanf("%s", s);
    int num=0, sum=0;
    bool sub = false;
    for(int i=0; s[i]; ++i){
        if('0' <= s[i] && s[i] <= '9'){
            num = 10*num + (s[i]-'0');
        } else {
            if(!sub) sum += num;
            else sum -= num;
            num = 0;
            sub |= s[i] == '-';
        }
    }
    if(!sub) sum += num;
    else sum -= num;
    
    printf("%d", sum);
    return 0;
}

1080 - 행렬

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

왼쪽에서 오른쪽으로, 위에서 아래로 한 칸씩 확인하면서 3x3크기의 부분행렬이 서로 다르다면 바꾼다. 마지막에 바꾼 횟수를 출력하면 정답이다.

이런 그리디가 통할 수 있는 것은, 이미 지나간 부분(탐색한 부분)에서 서로 다른 칸이 존재하면 안되기 때문이다.

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

int h, w;
char A[50][51];

void flip(int y, int x){
    for(int i=y; i<y+3; ++i){
        for(int j=x; j<x+3; ++j){
            A[i][j] = !A[i][j];
        }
    }
}

int main(){
    scanf("%d %d", &h, &w);
    for(int i=0; i<h; ++i) scanf("%s ", A[i]);
    for(int i=0; i<h; ++i){
        char s[51];
        scanf("%s ", s);
        for(int j=0; j<w; ++j){
            A[i][j] = A[i][j] == s[j];
        }
    }
    
    int ans = 0;
    for(int i=0; i<h-2; ++i){
        for(int j=0; j<w-2; ++j){
            if( A[i][j] == 0 ){
                flip(i, j);
                ans += 1;
            }
        }
    }
    
    for(int i=0; i<h; ++i){
        for(int j=0; j<w; ++j)
            if(A[i][j] == 0) return puts("-1"), 0;
    }
    
    printf("%d\n", ans);
    
    return 0;
}

2865 - 나는 위대한 슈퍼스타K

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

본선에 $K$명만 나갈수 있다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

굵은 글씨가 문제의 핵심인 것 같다. 각 참가자의 제일 높은 점수를 더하면 된다.
$K$명만 선발해야하므로, 최고점수가 높은 순으로 $K$명을 고른다.

1700 - 멀티탭 스케줄링

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

멀티탭에 k개 이상 꽂아야하는 순간 하나를 뽑는다. 뽑아야할 녀석은 가장 나중에 사용되는 플러그부터 뽑는다. 그런게 없다면 아무거나 뽑는다.

2816 - 디지털 티비

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

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

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

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

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

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

1783 - 병든 나이트

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

처음에는 무슨 탐색문제인가 했다가 N, M 이 2,000,000,000 인거 보고 기겁했다.

차근차근 읽어보니 나이트는 무조건 오른쪽으로밖에 이동할 수 없었다. 그렇다면 말이 방문할 수 있는 최대 칸은 M 일것이다! (1번과 4번을 반복한다면)

근데 N=2 이라면 무조건 오른쪽으로 2칸씩밖에 못 갈것이다. (2번과 3번을 반복) 그럼 최대 칸은 M/2 일 것이다.

N=1 이라면 말은 움직이지 못하고 항상 답은 1칸이다.

하지만 문제의 조건에서 이동 횟수가 4번 이상이면 1~4번을 한번씩은 해봐야 하는 것때문에 상당히 거슬린다.

N=1 은 항상 1이고, N=2 라면 갈 수 있는 최대 칸은 4칸밖에 안된다. (2번과 3번으로는 3회까지밖에 못 움직이기 때문)

위 두가지를 제외하고는 N이 몇이건 상관없다. 4회 이상을 이동할 수 있는 가로의 길이는 최소 7칸이다. 다시말하면, 4회 이상 이동하려면 2칸의 손해를 봐야한다. (1번~4번을 모두 사용하면 2번, 3번 때문에 1칸+1칸을 건너뜀)

정리하면 아래와 같다.

N=1, 답은 1
N=2, 답은 min(4, (m+1)/2)
N>2 이면서 m<7 이면 min(m, 4)
N>2 이면서 그 외의 경우에는 m-2

9009 - 피보나치

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

주어진 정수 X를 X와 같거나 가장 가까운 작은 수로 계속 빼면 된다.
마치 동전을 큰 단위부터 거슬러주면 제일 적은 개수로 거슬러 줄 수 있듯이,
가능한 큰 수로 계속 빼면 그것이 최소 개수로 표현할 수 있는 피보나치 수의 합이다.

ACM ICPC 2012 인터넷예선 D번 Fibonacci Numbers