컴퓨터 - ACM ICPC
16/08/09 21:36(년/월/일 시:분)
막대기
d[i][j]=1~i번 막대기를 사용해서 총 j길이를 만드는 경우의 수
d[0][0]=1
d[1][0]=d[0][0]
d[1][1]=d[0][1]+d[0][0]...
1,2,3으로 5를 만드는 경우
0 1 2 3 4 5
0 1 0 0 0 0 0 (한번도 안쓰는 경우를 1로 침. 즉 0을 0번 써서 0을 만드는 것)
1 1 1 1 1 1 1
2 1 1 2 2 3 3 (2를 뺀 경우, 위에서 2칸 앞의 것들을 가져옴) 하나 뺸 경우 2칸 앞, 두개 뺸 경우 2칸 앞 + 4칸 앞....
3 1 1 2 3 4 5 (3을 뺸 경우, 위에서 3칸 앞의 것들을 가져옴) 3칸앞+6칸앞+....
정렬이 안되있어도 상관없음
1,2,5 막대기를 사용할 경우
0->1->2->5 순서로 풀던
0->5->2->1 순서로 풀던 상관없음. 답이 같음.
O(KN^2) D[i][j] += D[i-1][j - k*L[i]];
O(KN) D[j] += D[j-a];
합분해
d[i][j]=i까지의 정수 j개를 써서 합이 i가 되는 경우의 수 (순서가 바뀐 경우도 다른 경우로 세고, 같은 수도 여러번 쓸 수 있음)
d[i][j][0] 0을 포함하는 경우
[1] 0을 포함하지 않는 경우
----
d[i][j]=숫자를 i번 더해서 j를 만드는 경우의 수
=d[i-1][j] +d[i-1][j-1] + .... + d[i-1][0]
마지막에 0을 더하는 경우 1을 더하는 경우
매번 더할때마다 MOD연산 해줘야 함 %1000...
--> V=A+B if(V>=MOD) V -= MOD; 이렇게 하면 MOD 연산횟수를 줄일 수 있어서 조금 빨라짐
new night
한 나이트가 다른 나이트를 한번에 잡을 수 있는 위치에 놓아서는 안된다.
나이트의 방향상, 윗줄 먼저 하고 아랫줄을 판단하면 된다.
현재 줄에서 윗줄만 겹치는지 파악하면 된다.
윗줄을
1번째: [0][0][1][0][0][1] 이렇게 배열로 표현하고
0=불가능
1=가능
2번째: .................. 배열로 표현
--> 이를 2진수로 간략하게 표현한다
1번째: 2^10 가지수
2번째: 2^10 가지수
= 2^10 * 2^10
d[1][000000(2)]
101001(2)
001001(2)
d[2] = d[1] 중에 max() + d[2] 1의 갯수
3칸 예를 들면
[1] = 000
100
010
001
101 5가지
그러면 그 다음에
[2] = 000 이면 max([1]...) + (000)의 1의 갯수
100 --> 이러면 [1]에서 불가능한 경우가 생긴다. 이것을 빼고 max() + (100)의 1의 갯수
단, 장애물이 있는 경우는 제외해야 하므로 마이너스 무한대 값(예: -1, 0...)을 넣어주면, max() 구하면서 자연스럽게 빠질 것
이렇게 하면 한칸 한칸 찾는게 아니라,
한줄 한줄 찾으므로 속도가 더 빠르다.
가장 많은 수
1. 일단 정렬을 시키고 : O(NlogN)
2. 앞에서부터 순차적으로 찾아나간다 : O(N)
지은이가 지은 집
수열 A 중에서
A[i],A[j]를 골라서
A[i]+A[j]=X가 되는 값을 찾는 문제. (답이 여러개일 경우, 가장 차이가 큰 것)
일단 정렬을 시켜놓고,
1 2 7 8
합이 10인 경우
맨 앞에 1에 대해서, 9을 찾으면 된다. (이때 이분탐색)
그런 식으로 1,2,7,8 차례차례 찾아보고
여러 답 중에서 A[j]-A[i]가 제일 큰 것으로 찾음.
-->근데 1 2 5 5 7 이렇게 5가 겹칠 경우 처리가 복잡해진다.
다른 풀이)
1 2 7 8
x-> <-y
x+y>10인 경우, y--
x+y<10인 경우, x++
근데 답을 찾은 경우, x=y이면 중복이니 답이 아님
1 2 5 5 7 이렇게 되면 5,5를 찾아도 x
1 2 5 7 이렇게 되면 5,5를 찾으면 x=y
시간복잡도는 (정렬 제외)
1번 풀이는 O(NlogN)
2번 풀이는 O(N)
집합
A,B가 정렬되어있다고 하면,
C를 만들때 A,B를 꼬이게 꺼내는 것은 항상 손해임
A 10 20 35
B 30 40
C 5 10
증명
A1 <= A2
B1 <= B2 일때,
꼬이게 하는 경우: |A2-B1|+|A1-B2| 이것이
안 꼬이게 하는 경우: |A1-B1|+|A2-B2| 이것보다 항상 크거나 같다.
꼬이면 더 커진다.
안 꼬이게 하려면, 작은 쪽을 기준으로 생각을 했을때
A 큰 집합
B 작은 집합
d[i][j]=A에서 1~i번 사용
B에서 1~j번 사용
하는 C배열의 합
d[i][j]=min(d[i-1][j], d[i-1][j-1]+|A[i]-B[i]|_
Ai를 제외한 값
최종 답은 d[n][m]
A B 0 30 40
0 0 무한대 무한대
10 0 20 무한대
=min(무한대,0+|20-10|)
20 0 10 40
=min(20,0+|30-20|) =min(무한대,20+|40-20|)
35 0 5 15
=min(10,0+|30-35|) =min(40,10+|40-35|)
개구리
여기서 N^2 배열을 다 찾으려고 하면 너무 오래 걸리고
4방향으로만 움직인다고 한정해서 풀어야 함
정렬을 2번 할 것임
x,y축을 단순화
(x-d,y+d) (x+d,y+d)
↖ ↗
o(x,y)
↙ ↘
(x-d,y-d) (x+d,y-d)
이것을
X=x+y
Y=x-y
이렇게 바꾸면 X,Y축에서 상하좌우로 움직이는 것과 같다
↑
← o(X,Y) →
↓
이것을 다시 x,y를 찾으려면
x=(X+Y)/2
y=(X-Y)/2
이러면 됨.
그 다음, 연잎들을 Y축,X축 순서로 정렬해서 번호를 매기면
Y
↑ 9 10 11
4 5 6 7 8
1 2 3
→X
여기서 1,2번은 Y축이 같고 인접하므로, 움직일 수 있다.
3,4번은 Y축이 다르므로, 움직일 수 없다.
이를 기억한다.
1 2 3 4 5 6 7
A 2 3
B
C 1 2
D
이러면 A,C방향만 찾을 수 있다.
B,D방향도 찾으려면 X축,Y축 순서로 다시 정렬을 하고 찾는다.
이러면 그래프 순서대로 따라가면 된다.
근데 문제는, 움직이면 현재 연잎이 가라앉는 것.
예를 들어 6번을 지나서 없어진다고 하면,
그래프를 업데이트 해줘야 한다.
Y
↑ 9 10 11
4 5 x 7 8
1 2 3
→X
6번이 있던 자리가 없어지면,
5,7번이 직접 이어질 것이고 (A,C방향에 직접 이어지도록 찾아서 업데이트)
2,9번이 직접 이어질 것이다.(B,D방향 업데이트)
그래프가 끊어지는 경우에는, 값이 지워지도록 업데이트
이렇게 하면 답을 찾을 수 있다.
개구리
여기서 N^2 배열을 다 찾으려고 하면 너무 오래 걸리고
4방향으로만 움직인다고 한정해서 풀어야 함
정렬을 2번 할 것임
x,y축을 단순화
(x-d,y+d) (x+d,y+d)
↖ ↗
o(x,y)
↙ ↘
(x-d,y-d) (x+d,y-d)
이것을
X=x+y
Y=x-y
이렇게 바꾸면 X,Y축에서 상하좌우로 움직이는 것과 같다
↑
← o(X,Y) →
↓
이것을 다시 x,y를 찾으려면
x=(X+Y)/2
y=(X-Y)/2
이러면 됨.
그 다음, 연잎들을 Y축,X축 순서로 정렬해서 번호를 매기면
Y
↑ 9 10 11
4 5 6 7 8
1 2 3
→X
여기서 1,2번은 Y축이 같고 인접하므로, 움직일 수 있다.
3,4번은 Y축이 다르므로, 움직일 수 없다.
이를 기억한다.
1 2 3 4 5 6 7
A 2 3
B
C 1 2
D
이러면 A,C방향만 찾을 수 있다.
B,D방향도 찾으려면 X축,Y축 순서로 다시 정렬을 하고 찾는다.
이러면 그래프 순서대로 따라가면 된다.
근데 문제는, 움직이면 현재 연잎이 가라앉는 것.
예를 들어 6번을 지나서 없어진다고 하면,
그래프를 업데이트 해줘야 한다.
Y
↑ 9 10 11
4 5 x 7 8
1 2 3
→X
6번이 있던 자리가 없어지면,
5,7번이 직접 이어질 것이고 (A,C방향에 직접 이어지도록 찾아서 업데이트)
2,9번이 직접 이어질 것이다.(B,D방향 업데이트)
그래프가 끊어지는 경우에는, 값이 지워지도록 업데이트
이렇게 하면 답을 찾을 수 있다.
K번째 수
quick sort 응용
1. pivot을 잡음 --> 맨 앞에걸 가져오기보다는,
랜덤으로 찍어야 속도가 더 잘 나옴
pivot 기준으로 작은거, 큰거로 파티션을 나눠줌
2. 원래는 양쪽 파티션을 다 들어가야 하나,
우리가 관심있는 부분은 k 번째이므로, k보다 작은 부분은 정렬이 안되도 상관없다.
그러므로 k보다 큰 부분만 정렬을 시킨다.