Team Tic Tac Toe

문제 설명

• Tic Tac Toe 게임을 하는데, 한명이 이길 경우와 2명이 팀을 이룰 경우 이길 경우를 구하라는 문제

풀이

• 한명이 이길 경우는, A ~ Z 까지 모든 사람들이 이길 경우의 수를 다 고려해주고, 두명이 이길 경우는 (A, B) ~ (Y, Z) 까지의 모든 경우의 수를 고려하면 해결할 수 있다.

Milking Order

문제 설명

• 소들의 우선순위와 초기 위치가 주어졌을 때 1번 소가 위치할 수 있는 곳들 중 인덱스가 가장 작은 곳을 구하라는 문제

풀이

• 먼저 소들의 초기 위치를 구해준 다음, 2가지 경우를 처리해 주면 된다.

• 우선순위에 1번 소가 속하는 경우
  • 앞에서부터 비어있는 자리에 우선순위에 따라 넣어주면
• 우선순위에 1번 소가 속하지 않는 경우
  • 가장 마지막자리부터 우선순위에 따라 부여하고 비어있는 자리 중 가장 앞에 있는 곳을 찾으면 된다.

Family Tree

문제 설명

• 정점들이 트리 형태로 주어지고, 2개 정점의 관계를 문제에서 주어진 규격에 맞게 출력하라는 문제

풀이

• 두 개의 입력을 A, B라고 가정했을 경우, 먼저 각 정점들의 부모를 구한 다음, 경우의 수에 맞게 처리
  • A 부모와 B 부모가 같은 경우 -> SIBLINGS
  • A의 부모(부모의 부모, ...)가 B인 경우 -> Mother
  • A의 부모(부모의 부모, ...)가 B의 부모인 경우 ->aunt
  • A, B가 연결되어 있는 경우 -> COUSINS
  • 아무것도 아닌 경우 -> NOT RELATED

Lemonade Line

문제 설명

• 소들이 레몬에이드를 먹기 위해 줄을 서는데 줄이 자신이 기다릴 수 있는 길이면 기다리고, 그렇지 않으면 줄을 서지 않는다. 소들이 가장 짧게 줄을 설 수 있도록 소들을 배치하라는 문제

풀이

• 소들을 내림차순으로 정렬하는게 이득이므로, 내림차순으로 정렬한 뒤 설 수있는 길이를 구하면 된다.

Hoofball

문제 설명

• 소들이 일직선 상 임의의 위치에 서 있는데, 공을 가지고 있는 경우 양 옆에 존재하는 소들 중 가장 짧은 소에게 공을 넘긴다. 모든 소들이 최소 1번 공을 만지기 위해 사용해야하는 공의 개수를 구하라는 문제

풀이

• N이 100이라서 어떤 풀이를 사용해도 된다. 나는 먼저 각 소에 공을 줬을 경우 갈 수 있는 소의 구간을 다 구하고 정렬을 시킨 뒤, 선을 가장 적게 사용하여 구간을 다 덮을 수 있는 문제로 변형해서 해결

• 다른 방법이 더 깔끔하고 좋다고 생각

Snow Boots

문제 설명

• N개의 발판이 있고, 각 발판은 눈에 덮여 있는데 발판마다 덮여있는 양이 다르다. 신발이 B개 주어지는데 각 신발은 발판에 덮여 있는 양에 따라 발판을 밞을 수 있고 밞을 수 없고, 신발들 중에서 가장 위에 있는 신발부터 빼서 사용하는 방식으로 진행된다. 위 규칙대로 진행할 경우 신발을 최소 몇개 사용하여 끝까지 이동할 수 있을까?

풀이

• dp[x][y] : x번째 위치에 있을 때, 쓸 수 있는 신발이 y인 경우 최소 버리는 횟수

• dp[x][y] = go(x, y + 1) : 신발을 바꿔신는 경우

• dp[x][y] = go(x + i, y) : 해당 신발을 그대로 신고 이동하는 경우

int d[251][251];
int n, m;
vector<pair<int, int>> v;

// v.first = 신발이 밟을 수 있는 눈의 양
// v.second = 신발이 갈 수 있는 최대 길이

int go(int x, int y) {
    if (x >= n - 1) return y;
    if (y >= m) return 1e9;
    int &ret = d[x][y];
    if (ret != -1) return ret;
    ret = go(x, y + 1);
    if (a[x] <= v[y].first) {
        for (int i = x + 1; i <= min(x + v[y].second, n - 1); i++) {
            if (a[i] <= v[y].first) {
                ret = min(ret, go(i, y));
            }
        }
    }
    return ret;
}