2016년 3월 20일 일요일

10472 - 십자뒤집기

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

3x3칸 크기의 보드를 1자로 펼치면 000 000 000 의 형태가 나온다. 각 칸의 상태를 */. 을 0/1로 표현하면 $2^9$ 가지 상태가 있다.

각 칸의 인접한 동서남북과 자신을 표현하면 아래와 같다.

int click[9]={
    416, //110 100 000
    464, //111 010 000
    200, //011 001 000
    308, //100 110 100
    186, //010 111 010
     89, //001 011 001
     38, //000 100 110
     23, //000 010 111
     11, //000 001 011
};

그리고 이 값을 XOR하면 그 칸을 선택하여 십자로 뒤집은 결과가 된다. 예를 들어, 101 000 010 의 가장 왼쪽 위칸을 십자로 뒤집으면 010 010 010 인데, 이건 101 000 010 XOR 111 010 000 이다.

너비 우선 탐색을 사용하여 000 000 000 부터 0~8번째 칸을 하나씩 뒤집어보면서 주어진 보드의 상태와 같아질 때 뒤집은 횟수를 출력하면 된다.

2016년 3월 15일 화요일

1138 - 한 줄로 서기

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

N명이 줄을 서는 모든 가짓 수 중에서 정답을 만족하는 경우를 출력했다.

N명이 줄을 서는 경우의 수 = O(N!)
매 번 조건에 만족하는 지 확인 = O(N)

next_permutation 을 썼다.

2098 - 외판원 순회

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

문제 <외판원 순회 2>의 실행시간이 오래 걸리는 이유는 모든 정점을 방문했는 지 확인하는 반복문이미 방문한 경로의 불필요한 탐색때문이다.

비트마스킹을 통해 이러한 반복을 줄여보자. 정점의 개수는 최대 16이다. 0번째, 1번째, ... 15번째를 방문했는지를 비트마스킹을 통해 00.....0 과 같이 길이가 16인 2진수로 표현할 수 있다. 그럼 $O(1)$만에 종료 조건을 확인할 수 있다.

하지만 모든 경우를 탐색하는 것은 똑같아서 수행시간에 큰 차이는 없을 것이다. (N배 빠르니까 약 10배)

여러 정점을 방문하면서 남은 정점을 확인할 때 중복되는 경우가 많다. 예를 들면 1 2 5 3 4 순으로 방문한 경우와 2 1 5 3 4 순으로 방문한 경우는 둘 다 1, 2를 방문한 상태에서 5 3 4 를 다시 방문하고 있다. 5 3 4 순으로 방문했을 때의 최적값을 구해둔다면 다시 방문할 필요 없이 미리 구한 최적해를 사용하면 된다. (메모이제이션으로 구현함)

이전에 작성한 에서 소스의 다른 부분은 모든 정점을 방문했는 지 확인하는 반복문을 없애고 O(1)의 비트로 확인한다는 점과, 메모이제이션을 적용했다는 점 밖에 다르지 않다.

2718 - 타일 채우기

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

2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.

문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.

2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다.

[그림 1] 한 줄의 상태를 비트로 표현할 때의 정수

이 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 1]에서 점은 빈 칸이고, x는 이미 타일로 채워진 칸이다 (그것이 어떠한 형태이건 채워졌다라는 상태만 의미한다.)

물론 [그림 1] 에서 1111 은 빠져있다. 필자는 1111을 0000과 동일한 상태로 봤기 때문이다. N일때 한 줄의 모든 칸이 다 차있다(1111)면 이것은 (N-1)에 대한 문제가 된다. - 자세한 것은 2N 타일링 문제 풀이 참조 - 따라서 1111 일때는 다음의 다음 칸(N-2)의 상태가 0000인 것과 같다.

그럼 한 줄의 상태로 모든 상태를 어떻게 표현하는가?
앞으로 채워야할 오른쪽의 타일에 대해 (위처럼 0000과 같이 표현된) 현재 상태로부터 진행될 수 있는 경우는 아래 그림과 같다.

[그림 2] 어떠한 상태로부터 진행될 수 있는 타일의 새로운 상태

파란색 점선 박스를 다음으로 채울 오른쪽 줄이라고 하자. 그럼 0000 으로부터 나오는 경우는 1001, 1100, 1111, 0011, 0000 과 같다. 마찬가지로 나머지 경우도 동일하다.

그렇다면 문제는 아래와 같이 쪼개어 표현이 가능하다.

f(N칸을 채우는 경우, 현재 상태) = 현재 상태로부터 만들 수 있는 다음 상태(N-1)의 개수

N이 0이 되는 순간 모든 줄을 확인했다는 의미이고 이 때의 상태가 0000(혹은 1111)이면 모든 줄을 채웠다는 의미이므로 하나의 개수로 치고, 그 외에는 잘못된 경우이다.

0000 -> 1111 -> 0000 을 한번에 넘어가는 N-2 때문에 N < 0 인 경우가 나온다. 이 때는 상태에 상관없이 불가능한 경우이므로 0 이다.

더보기


소스 코드

JOI 2015/2016 qualifying round

JOI 2016 예선
Online Judge: https://www.acmicpc.net/contest/view/152

크롬에서 한국어 번역 기능을 써서 문제를 읽었다. 문장이 이상하면 영어로 번역했다.

문제 #1. 科目選択

(물리, 화학, 생물, 지구과학) 중 상위 점수 3개 + (역사, 지리) 중 상위 점수 1개
두 묶음을 나눈 뒤 정렬하고 더함.

문제 #2. ゼッケンの交換

문제에서 설명한대로 구현하면 정답.
a[j] mod k > a[j+1] mod k 이면 자리를 바꾼다. k를 2부터 m까지 진행한 후 배열 a의 상태를 출력한다.

문제 #3. ロシアの旗

주어진 국기를 러시아 국기의 형태로 바꿔야하는 데, 최소 몇 개의 칸의 색깔을 바꿔야 하는 지 출력하는 문제이다.

위에서부터 (흰색, 파란색, 빨간색) 의 형태이여야한다. 나올 수 있는 모든 경우를 만들어보고 최소값을 갱신했다. $O(N^{3}M)$
N이 작아서 괜찮다.

나올 수 있는 모든 경우는 [0, i) 이 흰색 / [i, j) 이 파란색 / [j, n) 이 빨간색 구간인 것이다.
매 경우마다 N*M만큼 돌면서 색이 다른 칸의 수를 셈.


문제 #4. JOI国のお散歩事情

개미 문제처럼 사람들의 위치와 진행 방향이 주어지면 T 초 후 Q 사람들의 위치는 어디인가 묻는 문제이다. (사람들은 위치가 겹치면 그 자리에서 멈춘다.)

i번째 사람에게서 진행 방향에 따라 -T 혹은 +T 를 한 것이 그 사람의 T초 후의 위치일 것이다. i번째 사람의 나중 위치가 i-1번째 사람보다 앞서있다면 둘은 충돌한다는 것이다. 그럼 두 사람이 멈추는 위치는 (a[i]+a[i-1])/2. 그리고 이 위치로부터 더 이전 (i-1번째보다 더 이전) 에 있던 사람들도 이 위치에서 멈춰야하므로 모두 다시 갱신한다.

문제 #5. ゾンビ島

N개의 마을 중 K개 마을은 좀비에게 지배되었고 K개의 마을로부터 S개 이하의 도로만큼은 숙박 요금이 다르게 적용된다. - 정확히는 요금 Q를 적용, 그 외에는 요금 P를 적용 - (단, 좀비에게 지배된 K개의 마을은 지날 수 없다), 그리고 마을을 지날때마다 숙박 요금(P 또는 Q)를 낸다.
1번 마을로부터 N번 마을까지 가는 최소의 숙박 비용을 구하는 문제이다.

BFS로 K개 마을로부터 S개 이하의 도로(주변 거리라고 생각하면 됨)로 갈 수 있는 마을은 요금 Q를 적용한다.

노드마다 가중치를 두고 최단경로 알고리즘을 사용하면 된다.
노드에 가중치를 둘 줄 몰라서(!) 안전한 마을->위험한 마을 = Q, 위험한 마을>안전한 마을 = P 로 두고 다익스트라를 사용했다.
마지막 마을은 숙박비를 제외한다.

2016년 3월 11일 금요일

2661 - 좋은수열

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

처음에는 Naive한 코드를 만들었다. N<20 정도에 대해서 출력을 살펴보기로 한 것이다. 출력이 아래와 같았다. (출력 자체만으로 힌트는 충분했다.)

1
12
121
1213
12131
121312
1213121
12131231
121312313
1213123132
12131231321
121312313212
1213123132123
12131231321231
121312313212312
1213123132123121
12131231321231213
121312313212312131
1213123132123121312

앞의 수열이 계속 유지되면서 위에 1/2/3 중에 하나가 계속 붙는다. (자세히보면 N=7 과 N=8 인 수열은 조금 다르다.)

이전의 수열($a_k$)에 1/2/3 중에 하나를 붙여서 "인접한 두 개의 부분 수열이 동일한 것이 있는 지"를 확인하고, 없다면 조금 더 이전($a_{k-2}$)부터 다시 만들어보면 된다.
이렇게 하면 k-2 부터 다시 재귀를 하는건데, (1/2/3을 선택)^3 = 9번만 해보면 되니까 얼마 안걸린다. (이전의 수열은 유지된다)

2320 - 끝말잇기

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

단어를 첫글자와 마지막글자로 압축하고 재귀로 다음 단어가 가능하다면 진행하도록 했다.

매번 0~N-1 번째 단어를 모두 확인해야한다. (선택한 단어에 따라 가능한 단어가 바뀌기 때문)

이렇게 하면 16^16 인 것같다. 너무 많다. (16! 일수도 있는데 이것도 큼) 단어를 선택함에 있어서 순서만 다르고 조합이 같은 중복 선택(호출)이 분명 존재한다.

AE EA UA AU 같은 경우는 AE-EA-AU-UA 도 되지만, AU-UA-AE-EA 도 된다. (둘은 같다)

IE EE EI EO 는 EI-IE-EE-EO 도 되지만 EE-EI-IE-EO 도 된다. EO 입장에선 앞에서 무슨 순서로 오는 건 상관없다. 어떤 것을 사용했는가만 알면 된다.

N=16 이니까 n번째 단어를 사용했다/안했다고 표현하면 2^16 으로 표현이 가능하다. 그럼 재귀식은 (현재 위치, 이전까지 사용한 단어의 상황) 으로 중복을 제거할 수있다.

4299 - AFC 윔블던

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

두 팀이 득점한 점수의 합과 차가 주어졌을 때, 두 팀의 성적을 출력한다.

두 팀의 성적은 a, b라 하고 합을 S, 차를 D 라고 하면 $$
\begin{cases}
a+b = S \\[2ex]
a-b = D & \text{(a $\ge$ b)}
\end{cases}$$ 이다.

다시 말하면, a = (S+D)/2, b = (S-D)/2 이다.

두 팀이 서로 경기를 했으니 a, b 는 짝수일수밖에 없고, 음수가 나와도 잘못된 입력이라는 의미이다.

1024 - 수열의 합

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

합이 N이고 길이가 L이 되게 만드는 수는 단순히 생각한다면 (N/L) * L 일것이다.
이 말은, N/L 의 양쪽으로 L 만큼의 범위내에서 정답이 존재한다는 것이다.
18을 예로 들면, L=2 일때는 [8 9] 혹은 [9 10] 중에 답이 있고, L=3 일때는 [3 4 5] ~ [6 7 8] 중에 있다는 것이다. (L=3 이면 답은 5+6+7)

이런 아이디어에서 출발해서 L을 점점 늘려가면서 정답을 찾았다.
구간을 설정하고 그 시작점이 원하는 답 N을 넘어가면 그 이상의 수는 더 살펴볼 필요가 없다. (왜냐면 그 수 이후로는 합쳐서 N이 나올수가 없다. 무조건 N 을 넘는다)

L=2 부터 L=100 까지 답을 찾고, 없으면 -1 을 출력했다.

2016년 3월 10일 목요일

1175 - 배달

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

2차원 평면에서 S부터 2개의 C블럭을 모두 도달하는 최단 거리 BFS인데 조건이 있다.

같은 방향으로 2번 이상 이동할 수가 없다.

원래 BFS를 할때 visit[N][M] 처럼 했다면, "어디쪽에서 왔는가"도 추가해야한다.

그리고 2개의 C블럭을 모두 도달해야 한다. 이것을 C0, C1 으로 부른다면 어떤 지점까지 움직였을 때, 문제를 얼만큼 해결했는 가를 4가지 상태로 나타낼 수 있다.

1. C0, C1 을 모두 못 찾았다.
2. C0 을 찾았다
3. C1 을 찾았다.
4. C0, C1 을 모두 찾았다.

(C0를 찾았다, C1를 찾았다) 로 표현한다면 00, 10, 01, 11 로 나타낼 수 있고, 이를 2진수로 본다면 10진수 0, 2, 1, 3 이다.

4번의 상태가 나올때까지, 같은 방향으로 진행하지 않으면서, 이전에 왔던 위치에 이전과 똑같은 움직임으로 다시 방문하지 않고 (visit[y][x][previousDirect]), 그 때의 '얼만큼 찾았는 가'의 상태마저 같지 않은 경우만 탐색하면 된다.

2016년 3월 8일 화요일

2816 - 디지털 티비

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

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

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

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

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

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

1236 - 성 지키기

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

모든 행과 열에 1명 이상의 경비원을 배치한다.

채워야 할 가로의 수를 R, 세로의 수 C라 한다면 min(R, C) 만큼의 경비원은 겹치는 것이 최소이다. (1명으로 2개의 겹치는 공간을 해결하는 것이 불필요한 경비원을 줄이기 때문)

그럼 위의 경비원으로 min(R, C) 만큼 채웠고, 남은 빈 칸(또는 줄)을 채우는 것이 문제인데, 어딜 가건 이미 줄(또는 칸)을 다 채웠기때문에 남은 빈 칸(또는 줄)에 아무렇게나 채우면 된다.

답은 R+C-min(R, C)

데이터 만드는 게 오래걸려서 파이선으로 만들어봤다.

랜덤 데이터 생성 소스 첨부

import random
N, M = random.randrange(1,25), random.randrange(1,25)
print N, M
for _ in range(N):
 s = ""
 for _ in range(M):
  s += "1" if random.randrange(1,10)==1 else "."
 print s

6156 - Cow Contest

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

처음에는 위상정렬인가 생각했다. 위상정렬로 어떻게 하지 생각하다가 필요없단 걸 깨달았다.
한 소가 나머지 소들과 한번씩 붙어봤다면 (모두를 알면) 자신의 순위를 알 수 있다.

소를 하나의 정점으로 생각하면 어떤 한 정점과 연결된 선의 갯수가 V-1(자신을 제외한 나머지)개 라면 순위를 알 수 있다.

들어오는 간선(indegree) + 나가는 간선(outdegree) = V-1 (문제에선 N-1) 이면 된다. 정점끼리 서로 연결되었는 지는 방향 그래프를 유지해야하고, 셀 때만 구분없이 세면 된다.

7 6
4 3
3 2
1 2
2 5
5 6
5 7

는 2번 소, 5번 소 = 2개 가 나와야 한다.

2671 - 잠수함 식별


오토마타로 해결한다는 힌트를 듣고 오토마타가 뭔지 찾아서 문제의 오토마타를 나름대로 그려보았다.


얼추 되는 거 같지만 10001100001 와 같은 예는 식별하지 못한다.

그래서 100+ 이후의 1+ 에 대해서 상태를 추가해서 좀더 세밀하게 만들었다.


오토마타를 처음 접했는데, 뭔가 그래프의 인접행렬과 유사한 느낌인 것 같아서 새로웠다.
위의 그림은 노트에 끄적거린 것을 그대로 옮긴거라 좀 정리가 안되어있다.

처음에는 7번 상태 없이, 5번 상태에서 1인 경우 다시 5번으로 돌아와 1+ 를 나타내려 했는 데 엉망이였다. 1이 조금만 반복해도 맞다고 되어버렸다.

1+ 의 형태를 반복하다가 0 이 나오면 새로운 100+ 패턴인지 01 로 끊어지는 패턴인지 구분할 수 있도록 7번 상태를 추가했더니 잘 돌아갔다.

빨간색 화살표는 식별을 못하는 FAIL 상태이고, 초록색 상태는 패턴이 올바르게 끝난 상태이다.


동일한 문제

1484 - 다이어트

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

현재 몸무게를 a, 기억하는 예전 몸무게를 b라 했을 때 $a^2 - b^2 = G$ 가 되는 모든 a를 출력한다.

$1^2$ 부터 $10000^2$ 를 모두 저장하고 $b^2 + G$ 가 되는 제곱꼴(= $a^2$)를 이진탐색으로 찾았다.

2016년 3월 7일 월요일

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

1062 - 가르침

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

k개의 알파벳을 학습하여 N개의 남극언어 중 몇 개를 읽을 수 있는가인데, 시간 복잡도 계산 안하고 그냥 재귀로 돌려봤다 (패기..!)

매번 모든 알파벳을 검사하기는 힘들다. 그리고 어차피 알파벳은 한번만 배우면 계속 쓰일 수 있다. 그럼 각 단어마다 알파벳의 존재여부를 체크하여 저장할 수가 있는데, 한 단어에서 x번째 알파벳이 사용되었다/안되었다(0/1) 로 구분하면 26자리 2진수 (최대 $2^{26}-1$) 로 표현할 수 있다. 그럼 ACE 는 0 00000 00000 00000 00000 10101 로 표현된다.
소스는 1번째...26번째로 해서 비트가 왼쪽으로 하나씩 밀려있다.

A~Z 중에 k개를 선택했을 때 읽을 수 있는 최대 단어의 갯수를 반환하면서, 그 최대값을 갱신하도록 했다.

그리고 "K개의 글자"에 남극언어에 들어가는 ANTA,TICA 도 포함되어야 한다. (이것때문에 한참 틀렸다) 즉, 5개의 글자(ANTIC)를 반드시 배워야한다는 것이다.

1389 - 케빈 베이컨의 6단계 법칙

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

무방향 그래프에서 모든 정점이 서로 얼마만큼 가까운지(최단경로)를 계산하는 문제이다.

모든 정점에 대해 각각 최단경로를 구해도 되지만,(다익스트라라면 $O(V(E+VlogV))$) 문제에서 조건이 2 ≤ N ≤ 100 이므로 플로이드 와샬 알고리즘$O(V^3)$을 사용해도 충분하고 소스가 깔끔하다.

소스 첨부

10882 - International meeting

회의 시각과 회의 장소의 시간대(UTC)가 주어지면 다른 나라들의 시간대로 변환해주는 문제이다.

회의 시각을 UTC+0 로 변환한 다음 입력되는 UTC로 다시 계산하여 출력하게 했다.

계산 과정에서 시간대가 음수가 나올 수 있으니 24시간을 더한 후 모듈러 연산으로 해결하였다.

UCPC 2015 I번

2016년 3월 3일 목요일

5679 - Hailstone Sequences

어떤 정수 H 로부터 시작한 헤일스톤 수열의 원소 중에서 가장 큰 원소를 출력하는 문제이다.

특별한 기술 없이 짝수이면 2로 나누고, 홀수이면 3을 곱한 후 1을 빼는 연산을 반복하면서 1이 될 때까지 반복하면서 최대값을 갱신하면 된다.

비슷한 문제가 더블릿에도 있다. (여기선 수열의 길이가 아닌 수열 전체를 출력한다.)
그리고 더블릿의 문제와 똑같은 문제가 BOJ에 따로 있다.


2730 - 오늘은 OS 숙제 제출일

원제: The Bank of Kalii (2005 Greater New York Programming Contest B)

약 18개월만에 풀었다. 6개월마다 도전한거 같은데 오늘 정답을 맞았다.

처음에는 time 함수를 썼는 데, 저지에서 허용하지 않아서 - 당시에는 허용하지 않았다. 허용한 시점은 내 기억이 맞다면 이로부터 몇일 뒤 (.....) - 이리저리 ctime 에 의지하면서 노가다하다가 망했었고

두번째 시도는 지금 보니까 윤년이면 1일을 추가하는데, 올바르지 못한 날짜에 대해서 처리를 못한 것 같다.

이번에도 비슷하게 접근했는데, 제출날짜와 예상 날짜(1년 전/올해/1년 후)의 차이가 가장 작은 예상 날짜를 출력하게 했다. 차이는 "0년 1월 1일부터 특정 날짜까지의 지난 일수"의 차이로 계산했고, 윤년이면 2월을 하루 더 세고, 윤년이 아닌데 2월 29일이면 무한대수(INF)를 반환하게 했다.

3075 - Astromeeting

미팅하는 사람들이 어떤 은하 k로 가는 비용이 최소가 되는 은하 k를 찾는 문제이다.
그러기 위해선 모든 정점 간의 최단 거리를 구해야하므로, 플로이드 와샬 알고리즘을 썼다.

이제 모든 정점 간의 최단 거리는 구해졌고, (한 정점 K 에서 미팅을 하는 사람의 은하 i)들의 각 비용의 합이 최소가 되는 순간 미팅 장소 은하 K를 갱신했다.

3896 - 소수 사이 수열

에라토스테네스의 체를 써서 2~1299709 까지 소수를 모두 저장하고 입력되는 정수 k에 대해 upper_bound(k) - lower_bound(k) 를 했다.

여기서 말한 upper_bound(k) 는 k와 같거나 k보다 작지 않은 가장 작은 수를 의미하고, lower 는 그 반대이다.

C++ 라이브러리에 있는 std::upper_bound 랑 std::lower_bound 로는 원하는 위치가 나오지를 않았다. 라이브러리 함수는 수가 같은 경우엔 그 다음 iterator를 반환하고 있었다. 그래서 직접 구현했다.

5557 - 1학년

모든 경우를 탐색하는 재귀 함수를 만든다.

형태는 func(position, sum) 과 같은 형태로 만들었다. "배열의 현재 position까지로 합이 sum이 되었을 때로 만들어 지는 경우의 수" 이다.

계속 2가지로 갈래를 뻗어나가면서 position이 N-1이 되는 순간 a[N-1] 과 같은 경우만 경우의 수로 세면 된다.

N이 꽤 크다보니 이대로는 $O(2^N)$ 이기 때문에 무조건 재귀는 힘들고, 메모이제이션을 적용하면 충분히 시간내에 정답을 받을 수 있다.

첫 숫자가 "무조건 선택"임을 무시해서 여러 번 틀렸다. 항상 조건에 조심해야겠다.

2016년 3월 2일 수요일

5052 - 전화번호 목록

주어지는 전화번호들을 사전순으로 정렬하고 어떤 문자열이 바로 다음 문자열의 접두어라면 고민없이 "NO" 를 출력하고 다음 테스트케이스로 넘어가면 된다.

다음 다음, 혹은 그 이전이나 이후와는 비교할 필요가 없는 게, 이전은 이미 비교가 끝났을 것이고, 다음 이후에 존재한다는 것은 바로 다음도 접두어라는 의미이기 때문이다.

1238 - 파티

처음에는 플로이드 와샬로 접근해봤다. 아니나다를까 N=1,000 이라서 $O(N^3)$ 은 시간초과였다.

처음으로 다익스트라를 구현해봤다.
잘 동작하는지는 모르겠고 흉내만 내는 것 같다.
#define INF 987654321

typedef pair<int,int> ii;

int dijkstra(vector<ii> adj[], int n, int s, int e){
    vector<int> cost(n, INF); /* s 로부터 i까지의 최소 비용 */
    priority_queue<ii /*(-weight, next)*/> q;
    q.push({0, s});
    cost[s] = 0;
    while(!q.empty()){
        int pos = q.top().second;
        int dist = -q.top().first;
        q.pop();
        
        for(int i=0; i<adj[pos].size(); ++i){
            ii& next = adj[pos][i]; /* (next, weight) */
            if(dist + next.second >= cost[next.first]) continue;
            q.push({-(dist+next.second), next.first});
            cost[next.first] = dist+next.second;
        }
    }
    return cost[e];
}
예제가 잘 나오길래 제출해봤는데 정답이 잘 나왔다. 시간이 좀 걸리는걸 보니 N이 좀 커지면 시간초과가 나올 듯 하다.

1377 - 버블 소트

문제의 코드는 작은 수를 오른쪽(큰 수)으로 옮겨가면서 정렬이 다 되었을 때 종료한다. 반복문에서 i의 증가 횟수는 이동한 수의 개수와 같은 데,

한 원소가 자신의 위치로 이동하는 최소 거리들 중 최대값과 같다.
다시 말하면, 가장 멀리 (오른쪽으로) 이동하는 원소의 거리이다.

Lower/Upper bound 를 사용하는 이유는 [ 3, 1, 7, 5, 3 ] 의 경우 3이 이동해야 하는 최소거리는 현재 3의 위치마다 다르기 때문이다.

3 1 7 5 3
1 3 3 5 7

첫번째 3의 경우에는 오른쪽으로 1만 이동하면 되고, 마지막 3은 왼쪽으로 2만 이동하면 된다. 첫번째 3의 입장에서는 lower_bound 를, 마지막 3의 입장에서는 upper_bound 를 사용하면 그 거리가 나온다.

1110 - 더하기 사이클

수를 계속 변환하다가, 이전에 이 숫자가 나왔다면 사이클을 종료한다.

왜냐하면 그 숫자부터는 다시 같은 변환이 되므로 반복되기 때문이다.

11571 - 분수를 소수로

1110 - 더하기 사이클 과 유사하게 풀었다.

소수점 자리가 반복되는 지점은 나눗셈의 나머지가 같은 부분이 나온다는 것이다. 같은 나머지 값이 나오면 그 부분부터 다시 반복되는건 당연한 사실이다.

우선 A/B 를 기약분수의 형태로 바꾼다.
손으로 나누기 과정을 직접 하듯이 수를 계속 나누면서 결과값(string)에 수를 계속 붙인다.
boolean값 배열을 놓고 연산 도중에 이미 나온 나머지값이 나온다면 나누기 작업을 중단한다. 그리고 이전에 그 나머지가 나온 순간부터 나누기를 중단한 곳 (현재 문자열의 끝) 까지가 반복되는 지점이라는 뜻이다.

반복되는 구간이 없다면 (0) 을 출력하고, 아니라면 반복되는 구간을 출력하도록 했다.

9009 - 피보나치

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

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

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

11568 - 민균이의 계략

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.

이 문제는 $O(N^2)$ 도 가능하다. 현재 자신보다 이전에 더 작은 수가 있다면, 현재값과 그 수까지의 LIS+1 중에 더 큰 값으로 선택하면 된다.

코드로 구현하면 아래와 같다.

int answer = 0;
for(i=0; i<n; ++i){
    for(j=i; j>=0; --j){
        if(a[j] < a[i]){
            LIS[i] = max(LIS[i], LIS[j]+1);
        }
    }
    answer = max(LIS[i], answer);
}
printf("%d", answer+1);

10971 - 외판원 순회 2

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

어떤 지점 s에서 출발해서 모든 정점을 거치고 다시 s로 돌아오는 경우를 모두 탐색했다. $O(N!)$
매 번 "모든 정점을 방문했는가?" 를 확인하면서 모두 방문했다면 현재가 s인가(출발점 == 종료점)를 판별해서 그렇다면 그때의 값이 최소가 되게 했다.

이동할 때마다 가중치를 더한다. 모든 정점을 방문했을 때 자신으로 돌아온게 아니라면 답이 아니도록 했다.

어떤 지점 s는 어디건 상관없다. 출발점과 도착점이 같은 지점을 찾는다면, 그 지점이 어디건 정답인 경우의 경로는 똑같이 나온다.

3745 - 오름세

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.
$N$이 적당히 크므로 $O(N^2)$ 은 안되고 $O(NlogN)$ 으로 해결해야 한다.

11880 - 개미

솔루션 듣고 어이가 없었다. 왜냐하면 하루종일 메달렸기 때문이다.

처음에는 임의의 점 P(x, y) 를 거쳐서 가는 최단 거리를 계산하려고 방정식을 하루종일 엄청 풀었는 데, 결국 답은 한 마디면 끝났다.

상자를 펼치면 된다. 그럼 (a+b)2 + c2 이 이동한 거리2 이다.

1208 - 부분집합의 합 2

1182 - 부분집합의 합 에서 시간 제한이 N=20 에서 N=40 으로 확장된 문제이다.

$2^{20}$ 은 약 100만이라 시간이 충분했지만, $2^{40}$ 은 1조에 가깝다.

문제를 아무리 봐도 좋은 생각이 안 나다가, 주변에서 몇가지 힌트를 받고 해결할 수 있었다.

N개의 정수로 이루어진 배열 a에서 모든 부분집합을 살피려면 위에 말한것과 같이 $2^{40}$ 이라 굉장히 힘들다. 하지만 반으로 나눠서 부분 집합을 살핀다면 이 문제를 해결할 수 있다.

배열 a를 반으로 나눈다. 즉, $ a_0, a_1, \dots a_n $ 을 $ a_0, a_1, \dots a_{n/2} $ 와 $ a_{n/2 +1}, \dots a_n $ 으로 나눈다.

그리고 $ a_0, a_1, \dots a_n $ 에서 나올 수 있는 부분 집합의 합을 A 라 하고 나머지 $ a_{n/2 +1}, \dots a_n $ 나올 수 있는 부분 집합의 합을 B 라 하자.

그럼 문제의 정답은 (A의 원소로만 가능한 경우) + (A+B로 가능한 경우) + (B로만 가능한 경우) 로 나타낼 수 있다.
각각의 배열을 만드는 시간은 $2^{20}$ 을 두 번 하면 되고, "A+B로 가능한 경우"는 배열 B에 S-A[i]의 원소가 있는 지를 확인하면 된다.

S=0 이고 a = [ -7, -3, -2, 5, 8 ] 같은 경우는 A = { [-7, -3] 으로 나타낼 수 있는 부분 집합들 } 이고 B = { [-2, 5, 8] 으로 나타낼 수 있는 부분 집합들 } 이다. 이를 자세히 적는다면 A = [ -7, -3, -10 ], B = [ -2, 5, 8, 3, 6, 11 ] 이다.
여기서 답은 (A의 원소로만 가능한 경우 = 0) + (A+B로 가능한 경우는 -3+3=0 으로 1개) + (B로만 가능한 경우 = 0) 으로 1 이다.

주의해야 할 점은, 원소가 같은 것이 여러 개 있을 수 있다. 예를 들어 A = [0, 2, 2], B = [2, 2, 4] 라면 각 숫자는 서로 다르기 때문에 따로 세어야하고 A+B 로 만들어지는 2+2 의 경우들도 모두 서로 다르게 조합된 것들이기 때문에 모두 세어야 한다. 같은 2+2 이지만 $A_1 + B_0$ 은 2 + 2 인 것이고, $A_2 + B_0$ 은 (0+2) + 2 이기 때문이다.

10216 - Count Circle Groups

개인적으로 재미있게 풀었다. 알고스팟 남극기지 문제처럼 좌표평면과 범위가 있어서 엄청 어려워보였다. (주의. 남극기지와는 다른 문제이다!)

시간 제한이 8초인건 나중에 봤고, N이 3,000 이하이길래 충분하다고 생각하고 코딩을 시작했다.

아이디어는 이랬다. (사실 문제에서 말한 그대로 하는거라 아이디어랄 것도 없다.)

아군의 통신 영역이 서로 닿거나 겹친다면 통신 가능하고, 통신이 가능한 부대끼리는 하나의 그룹처럼 이동한다. 여기서 그룹의 개수를 헤아리는 문제인데, 그렇다면 진영을 하나의 노드로 본다면, "몇 개의 그래프가 존재하는가"로 문제를 바꿔 생각할 수 있다.

정점 $A_i$ 에서 $A_j$ 로 통신 가능하다면 이동하도록 인접 리스트를 만든다. ( $O(N^2)$ )
각 정점에서 연결된 모든 정점을 방문하고 개수를 센다. (여기서 하나의 그래프를 발견) . 방문하지 않은 나머지 정점을 확인한다. ( $O(N^2)$ )

그래프를 세는 부분을 코드로 표현하면 아래와 같다.

bool dfs(vector<int> adj[], int pos){
    if(visit[pos]) return false;
    visit[pos] = true;
    for(int i=0; i<adj[pos].size(); ++i)
        dfs(adj, adj[pos][i]);
    return true;
}

memset(visit, false, sizeof(visit));
int count=0;
for(i=0; i<N; ++i){
    count += dfs(adj, i);
}
printf("%d\n", count);

지금 생각해보니 분리집합(Disjoint-set) 으로 했어도 괜찮았을것 같다.

1963 - 소수 경로

에라토스테네스의 체로 소수를 걸러내면서 4자리의 소수 1001 ~ 9973를 모두 저장했다.

소수 X 에서 1자리의 변화로 가능한 수를 "인접리스트"처럼 만들었다.
예를 들면, 1021에서 이동 가능한 다음 소수는 1031, 1051, 1061, 1091, 1321, 1621, 1721, 4021, 5021 이다.

이게 가능한 이유는

1. 소수에서 출발하여 소수로 끝난다.
2. 중간 과정에서도 항상 4자리 소수임이 유지된다.

이기 때문이다.

그리고 이렇게 만들어진 인접리스트로 BFS를 돌렸다.

처음에는 "특정 소수 S 에서 다음 소수 T 까지의 최소 거리"를 누적하면서 DP를 하려 했다.

vector<int> adj[9999]; /* 이 소수로부터 1의 변화로 갈 수 있는 인접 소수 */
 
int S, T; /* S에서 T로 만들어야 함 */
int dp[9999]; /* memset(-1, .. */
 
int f(int cur){
    if(cur == T) return 0;
     
    int& r = dp[cur];
    if(r != -1) return r;
    r = INF;
    for(int i=0; i < adj[cur].size(); ++i){
        r = min(r, 1+f(adj[cur][i]));
    }
    return r;
}

왜냐하면 시작 소수를 S, 목적지를 T, 중간에 거친 임의의 소수를 K 라고 하면 K->T의 최소와 S->K 의 최소가 곧 S->T 가 되는 최소 거리라고 생각했기 때문이다.

안되는 이유를 못 찾아서 결국 BFS로 했는데, 8179 1733 와 1733 8179 의 케이스에서 서로 다르게 나오는 데, 나중에 자세히 디버깅해봐야겠다.

참고로 시작점이 소수인 이상, 문제에서 말하는 불가능한 경우는 존재하지 않는다.

BFS로 해결하는 소스는 아래와 같다.

10573 - 증가하는 수

234까지 증가하는 수의 개수를 이렇게 표현해봅시다.
000~234 사이에 증가하는 수의 개수.
그럼 각 자리마다 압축된 표현을 할 수 있습니다. 이게 무슨 말이냐면 3자리로 표현되는 모든 증가하는 수를 나열해봅시다.
000      ------
001
...         이 구간의 개수 = (10-0)개 = 10개
009      ------
011      ------
012
...         이 구간의 개수 = (10-1)개 = 9개
019      ------
022      ------
...         이 구간의 개수 = (10-2)개 = 8개
029      ------
088
...         이 구간의 개수 = (10-8)개 = 2개
089      ------
...
111      ------
...         이 구간의 개수 = (9+8+...+1)개 = 45개
199      ------
111~199 구간의 개수는 (X11~X19) +(X22~X29) + .. 이기 때문에 45개입니다.

이런식으로 각 구간의 개수를 XXX ~ YY9 와 같은 식으로 표현할 수있습니다.
123까지의 증가하는 수는 (0XX~099) + (1XX ~ 123) 입니다.

이렇게 센다면 "각 자리마다 압축된 표현"이 가능합니다. 예를 들어, 123 에서 1은 0XX~099 까지를 표현하고 있습니다. 즉, (해당 자리의 수-1) 까지의 모든 개수를 담고 있습니다. 그리고 이 개수는 자리수마다 다르겠죠.

각 자리수마다 X~9 구간에 있는 수의 개수는 다음과 같습니다. (왼쪽에서 오른쪽으로 X=0 -> 9 를 의미함)

1자리(X~9) : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
2자리(XX~99) : 55, 45, 36, 28, 21, 15, 10, 6, 3, 1
3자리(XXX~999) : 220, 165, 120, 84, 56, 35, 20, 10, 4, 1

이런식으로 80자리를 모두 표현할 수 있습니다.

4457의 경우, 첫 자리의 4가 의미하는 건 (0XXX ~ 3999) 의 개수입니다. 여기에는 220 + 165 + 120 + 84 = 589개가 있습니다. 그리고 다음을 세어봐야하는데 다음은 4000 ~ 이 아닌 4444 ~ 임에 주의하시길 바랍니다.

즉, 두번째 자리의 4는 444 ~ 457 을 의미합니다. 이미 자리수가 같으므로 구간내(4XX~4XX)에서 나올 숫자는 없겠지요.

다음으로 세번째 자리는 44~57 를 의미합니다. 여기엔 (44~4X) = 6개가 존재합니다. 마지막으로 5~7 까지 3개를 더해주면 589+0+6+3 = 598개가 존재한다는 것을 알 수 있습니다.

2016년 3월 1일 화요일

2168 - 타일 위의 대각선

x=8cm 이고 y=12cm 인 대각선은 x=2cm 이고 y=3cm 인 대각선을 4배한 것과 같다.

그리고 x, y에 대해서 대각선이 그려지는 타일의 개수는 x+y-1개 이다.

위 두가지 정보를 조합하면 정답이 나온다.

11501 - 주식

메인 아이디어만 말하자면, "주가가 떨어지기 직전에 샀던 주식을 전부 팔아버린다." 이다.

모든 주식을 산다. 그리고 주가가 떨어진다면 기존에 샀던 모든 주식을 현재가로 매매한다.

이러면 "3. 아무것도 안한다" 는 고려할 필요가 없게 된다. 왜냐하면 다음 주가가 떨어진다면 현재가로 팔 것이고, 이 순간 현재가와 판매가는 같기 때문에 산 값 그대로 얻는다. 즉, 사지 않은 것과 동일하다.

아래 소스는 코드로 구현한 것이다.

Asia Regional - Daejeon 2015 I번 Stock

소스 보기

1072 - 게임

형택이가 앞으로 더해야 하는 판을 k 라고 할 때, 소수점을 버렸을 때, $\frac{Y+k}{X+k}$ != $\frac{Y}{X}$ 가 되는 가장 큰 정수 k 를 구하는 게 문제죠.

수의 변화가 일어나는 부분은 Y+k 가 2Y 가 되거나, X+k 가 2X 가 되는 경우인데, X만 증가하는 경우(지는 경우)는 없으므로 Y+k 가 2Y에 가까워지면서 $\frac{Y+k}{X+k} > \frac{Y}{X}$ 가 되는 정수 k를 구하면 됩니다.

비례방정식으로 아래처럼 나타낼 수 있습니다
$$ {Y+k} : {X+k} = 2Y : X $$
그리고 여기서 아래 수식을 만족해야 겠죠.
$$\frac{x^2}{\left(99x-100y\right)}\le k \in \mathbb Z$$
근데 수식으로 정리해서 했더니 잘 안되더군요.
답은 바이너리 서치로 해야하나봅니다.

근데 근사값을 계산할 때 주의해야 할 점은 위 식대로라면 k로 인한 차이가 0.01 을 넘기는 부분, 즉 $ \frac{y+mid}{x+mid} - \frac{y}{x} \ge 1e^{-2} $ 가 되어야 하지만,
소수의 부정확성 때문에 양 변에 100을 곱하여 1의 차이로 계산하면 됩니다. 다시 말해, $ 100\frac{y+mid}{x+mid} - 100\frac{y}{x} \ge 1 $ 와 같이 하면 됩니다.

1744 - 개근상

N일동안의 출석 기록은 OOOO와 같이 길이 N으로 표현될 수 있습니다.
각 위치가 의미하는 것은 i일 째의 기록을 의미합니다. 즉, 각 위치는 1일 째, 2일 째.. 와 같죠.
우선 전탐색을 생각해봅시다.
출석(O) / 지각(L) / 결석(A). 이렇게 3가지로 나누어 지는데, 각 날짜에 대해서 3가지 가능성을 모두 검토하면 $3^N$ 이라는 지수 시간이 걸리겠네요.3이라는 어마어마한 시간이 걸리겠네요.
하지만 모든 가능성을 검토해야하는건 사실이므로 소스를 짜봅시다.
대충 중요한 동작 부분만 의사코드로 작성해본다면
f(O, L, A){
    if(O+L+A > N) return 0;    // 모든 출결사항의 기록. 즉, O+L+A 는 기록된 날짜 수와 같습니다.
    if(O+L+A == N-1) return 1; // 마지막 날까지 기록을 모두 확인했다면 한 가지 경우의 수로 취급합니다.

    return f(O+1, L, A)
           + f(O, L+1, A);
           + f(O, L, A+1);
}
이렇게 작성할 수 있겠네요. 하지만 문제를 보면 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람은 제외 한다고 합니다.
그럼 지각이 두번 이상인 것은 어떻게 확인할까요?
f(O, L, A){
    if(O+L+A > N || L >= 2) return 0; // 지각이 두 번이상 체크되면 경우의 수로 취급하지 않음.
    if(O+L+A == N-1) return 1;

    int ret = 0;
    ret += f(O+1, L, A)
    ret += f(O, L+1, A);
    ret += f(O, L, A+1);
}
문제는 결석의 세 번 연속 등장을 어떻게 구분하는가 입니다. 방법은 간단합니다. 결석이 등장하지 않을 때는 (즉, 출석이나 지각인 경우에는) 결석의 횟수를 0으로 하면 됩니다. 대신 이렇게 되는 경우 O+L+A == N 의 공식이 무너지게 되므로, 날짜 수를 별도로 세어주도록 해야합니다.
f(O, L, A, days){
    if(days > N || L >= 2 || A >= 3) return 0; // 결석이 3번 이상 체크되면 경우의 수로 취급하지 않음.
    if(days == N-1) return 1;

    int ret = 0;
    ret += f(O+1, L, 0, days+1); // 연속이 끊김
    ret += f(O, L+1, 0, days+1); // 연속이 끊김
    ret += f(O, L, A+1, days+1);
}
이 함수를 단순히 메모이제이션하기만 해도 정답이지만, 메모리를 엄청 잡아 먹을것입니다.
현재까지의 코드는 분명 중복되는 부분이 있습니다. 조금만 더 생각해보신다면 중복을 제거하여 효율을 높일 수 있습니다.

1744 - 수 묶기

묶거나(=다음 수와 곱하거나) / 묶지 않거나(=그냥 더하거나) 를 모두 해보면 된다.

큰 수는 큰수끼리 곱해지는 것이 항상 큰 값을 얻을 것이다.

배열 a를 비내림차로 정렬한 후, 모든 경우를 살핀다면 아래와 같이 표현할 수 있다.

$$f(pos) = max( a_{pos} + f(pos+1), a_{pos} \cdot a_{pos+1} + f(pos+2) )$$

여기에 메모이제이션을 적용하면 된다.

3273 - 두 수의 합

$a_i + a_j = x$ 를 만들 수 있는 (i ,j)의 쌍의 갯수를 찾는 문제이다.

이를 변형하면 $a_i$ 에 대해서 $a_i = x - a_j$ 가 되게끔 하는 $a_j$를 찾으면 된다.

이진탐색을 이용하면 된다.

2629 - 양팔 저울

2629 - 양팔 저울 풀이입니다.

KOI 2001 초등부 2번
2가지 방법이 있네요. 저는 동전 교환 알고리즘(DP) 로 풀었습니다만, 대회 공식 풀이를 보니 휴리스틱을 추가한 재귀로 설명하네요. 구현의 차이일 뿐, 기초적인 발상은 똑같은 것 같습니다. 우선 글 주변이 없는 관계로 의식의 흐름 순서로 설명하는 점 양해를 구하겠습니다.

우선 문제에서 주어지는 조건들을 파악했습니다. 주어지는 추는 30개 이하이고, 모두 자연수이며, 같은 무게가 여러 개일 수 있습니다. 그리고 추는 500g 이하네요.

"주어진 추를 사용해서 구슬의 무게($x$ 라고 합시다.) 를 확인할 수 있는 가" 를 좀 더 수식처럼 바꿔보자면, 각 추를 $a_0, \dots a_n$ 으로 표현했을 때, $ x = a_0 * (0|1) + \dots + a_n * (0|1)$ 처럼 쓸 수 있을것 같네요. 여기서 (0|1) 은 사용하지않거나/사용하거나를 의미하는 수입니다.

근데 이 수식은 뭔가 부족하네요. 주어진 추로 $x$를 만들 수 있는가를 묻고 있지만, 구슬($x$)와 같은 쪽에 추가 달려있을 경우는 고려되지 않았네요. 다음처럼 바꾸면 해결됩니다.

$$ x = a_0 * (-1|0|1) + \dots + a_n * (-1|0|1)$$

방정식의 좌변/우변을 저울의 왼쪽/오른쪽으로 생각하면 좀 읽기 편해질겁니다. -1은 구슬과 같은 쪽에 매달았다는 뜻이 되는거죠.

이제 이 수식에 대한 답을 어떻게 구하는 가가 문제인데, $a_0, \dots a_n$을 하나씩 살피면서, 각 $a_i$($i$번째 추)에 대해
  • 구슬과 같이 올렸을 때(-1)
  • 올리지 않았을 때(0)
  • 반대쪽에 올렸을 때(+1)
이렇게 3가지 행동1개를 취할 수 있습니다. 예를 들어, $a = \{1, 4\}$ 라면 아래와 같은 경우의 수가 있겠네요.

저울의 중심 = |
 x   | 1
 x   | 4
 x   | 1 4
 x 1 | 4
 x 4 | 1

그렇다면 나올 수 있는 조합의 갯수는 $3^n$ 이겠군요! 주어진 추들로 만들 수 있는 모든 $x$를 구하면 되지 않을까요? 네. 이대로 돌린다면 안됩니다. $n$ 이 30개 이하니까 $3^{30}$. 대충 계산해도 $10^{14}$ 가 넘어가는 대수라 시간초과가 분명합니다.
참고로, 약 $10^8$번의 연산을 1000MS로 어림잡아 계산할 수 있습니다. (이것은 정확한 수치가 아니라 컴퓨터의 성능이나 환경에 따라 다릅니다! 시간 측정의 도움을 주는 척도로만 사용하세요.)

그럼 이 문제를 어떻게 해결할까요?

동전 교환 알고리즘(Coin Change Algorithm) 을 통해 해결할 수 있습니다. 간략히 설명하자면, "특정 단위의 동전들이 몇개 주어졌을 때, 이 동전들을 사용해서 x원을 만들 수 있는가?" 를 해결하는 알고리즘입니다.
이걸 이용해 모든 경우를 구한다면 이렇게 해결할 수 있습니다.
예시를 그대로 사용하겠습니다. 먼저, 1g짜리 추를 사용해 확인할 수 있는 경우 추의 무게는 (0g+1g/ 0g / 0g-1g) 입니다. 여기서 얻어진 -1g/0g/1g 에는 "1g짜리 추를 사용했다"라는 의미가 들어있습니다. 따라서 여기에 추가적으로 4g에 대해 살핀다면 "1g짜리와 4g짜리를 사용하여"와 같이 의미가 중첩되는 것입니다.
확인할 수 있는 추의 무게를 가진 배열을 $C$ 라고 하겠습니다. 그럼 $C$에는 처음에는 0g 이 들어있을 것입니다.

$$ C = \{ 0 \} $$

1g짜리 추를 사용하여 결과를 확인한 후에는 다음과 같습니다.

$$ C = \{ -1, 0, 1 \} $$

각 수들에 대해 4g 을 확인한다면

$$ C = \{ -5, 3, -4, 4, 5, -3 \} $$ 과 같습니다.

 여기서 수를 정렬하지 않은 것은, -5, 3은 -1로부터. -4, 5는 0 으로부터 나왔기 때문입니다.  즉, -5 = -1-4(1g과 4g을 구슬과 같은 쪽에) 이고 3 = -1+4(1g은 구슬과 같은 쪽, 4g은 반대 쪽)를 의미합니다.

이 문제에서 사실 우리는 음수를 고려할 필요가 없습니다. 왜냐하면 (위에서 표현한 대로 저울을 표현하자면) x 1 | 4 와 4 | x 1 는 같기 때문입니다.
이런 식으로 점차 추의 무게를 키워가며 확인한다면, 모든 추의 무게를 확인할 수 있습니다.
나올 수 있는 최대 무게는 500g의 추가 30개인 15000g입니다.

요약

어떤 추의 무게를 $x$라고 하면, 왼쪽에 올리면 $x$가 빼지고 오른쪽에 올린다면 $x$가 더해지는 것으로 이해할 수 있다. 이것을 이용하여 주어진 추들로 확인할 수 있는 모든 구슬의 무게 를 구하고, 그 구슬의 무게에 대한 질답에 답한다.
적절한 가지치기 혹은 동전 교환 알고리즘을 통해 모든 경우의 수를 구한다.

더보기

동전 교환 알고리즘

게시글 목록