2705 - 팰린드롬 파티션

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

7을 팰린드롬 파티션으로 표현하면 아래와 같다.

       7
   1+  5  +1
   2+  3  +2
  1+1+ 3 +1+1
  3+   1   +3
1+1+1+ 1 +1+1+1

가운데를 축으로 보고, 양쪽으로 갈라지는 수에 대해 다시 재귀적으로 그것들을 축으로 센다.

아래와 같은 점화식으로 표현 가능하다.
$$ f(n) = 1 + f(0) + \dots + f(n/2) $$
1은 자기 자신을 나타내는 가짓 수이기 때문에 매번의 분열마다 더해준다.

1730 - 판화

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

주어진 명령에 따라 팔을 움직이면서 자취를 그린다.

이미 그 곳에 자취가 그려져있는데 다른 방향이라면 + 를 그린다.

9518 - 로마 카톨릭 미사

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

다른 사람 소스를 보니까 내가 너무 어렵게 생각했던 것 같다.

(i, j)에서 주변 각 8방향에 대해 악수를 했다/안했다로 xxxxxxxx의 비트로 저장해서 주변 8방향을 하나씩 악수했다. (비트를 참고하여 이미 악수했다면 횟수로 세지 않았다.)

1507 - 궁금한 민호

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

(연결된 정점을 x-x 로 표현하겠다)
i-j-k 가 가능한 i-k 가 있다면 i-k 인 간선은 필요가 없다. 왜냐하면 i-k 는 i-j, j-k 로 표현이 가능하고, 같은 거리로 더 많은 도시를 갈 수 있도록 유지되기 때문이다.
결과적으로 필요한 간선만 남게 된다.

불가능한 경우는 잘못된 입력이 주어지는 경우이다. 이를테면 주어진 입력으로 a->b->c 를 해보면 a->c 보다 더 작게 나온다던가 그런 입력.

1445 - 일요일 아침의 데이트

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

다익스트라에서 선택해야할 우선순위 조건이 다음과 같이 2가지이다.

1. 지나가는 쓰레기의 수는 최소로
2. 쓰레기 근처를 지나는 칸의 수를 최소로

S에서 F까지 가면서 위 2가지의 가중치가 최소가 되게 선택하면서 진행하면 된다.

10217 - KCM Travel

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

주어진 비용으로 갈 수 있는 1번~모든 노드의 최단 거리를 구한다.

구하는 과정에서 아래와 같이 정보를 저장한다.

dp(i, k) = i번 노드까지 k의 비용으로 갔을 때의 최소 시간

주어진 비용 내에서 N번 노드까지 간 최소 시간을 구하면 된다.

1261 - 알고스팟

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

2차원 평면에서 큐를 넣고 빼고 하는 코드를 적으면 왠지 귀찮을꺼같아서 각 칸을 노드처럼 썼다. 예를 들면, 각 칸의 노드 번호는 아래와 같다.

// 4x2 크기의 평면
0123
4567

1인 칸으로 가는 경우에는 벽을 부숴야하므로 가중치가 1인 간선이 있다고 생각하면 된다. (그 외에는 가중치가 0인 간선)

그럼 다익스트라로 0번 -> h*w-1번 으로 가는 최단 경로 문제가 된다.

같이 보기

 - 알고스팟: BOJ