일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 카카오 인턴십
- 2629
- Longest Increasing Subsequence
- 2228
- LIS
- 카카오 인턴
- 알고리즘
- 여름인턴십
- 백준12015
- 백준
- 카카오 면접
- 기술면접
- 최장증가수열
- 개발자 면접
- 백준11053
- 정상회담2
- 카카오 자기소개서
- 2482
- 1670
- 백준12738
- 카카오 서류전형
- 구간나누기
- LIS 알고리즘
- DP
- 파이썬
- Python
- 인턴십 면접
- 가장긴증가하는 부분수열
- 카카오
- 단어수학
- Today
- Total
프로그래밍에 대한 고찰 및 생각
[알고리즘][6][백준_1670][Python3] - 정상 회담 2 본문
문제 이해
문제자체는 간단하지만 n이 조금만 커져도 경우의수가 커지고 점화식도 쉽게 발견되지 않아 조금은 까다로웠던 문제였다.
서로 팔이 교차하지 않는 것을 중점으로 생각해봐야 할것같다.
알고리즘 전략
점화식에 접근할때 n이 주어졌을때 그 상황들을 분해하려고 고민을 했다.
먼저 n = 8 일때로 먼저 분석을 해보자. ( 편의상 n=k일때 가능한 경우의 수를 dp[k]라고 하자 )
이 상황에서 악수를 할수 있는 경우의 수를 찾다보면 한가지 규칙을 찾을 수 있다.
어떤사람과 어떤사람이 악수할때 그 둘 사이에 있는 사람의 수가 홀수가 되면 안된다는 것이다.
따라서 파란색 점을 기준으로 할때 이 사람이 악수 할수 있는 사람은 위의 3점과 자신을 제외한 4개의 점이다.
파란색이 악수 할수있는 점은 다음과 같다.
이제 위의 4가지 경우들 안에서 가능한 모든 경우의 수들을 구한것이 dp[8]이 될것이다.
그런데 맨왼쪽과 맨오른쪽, 그리고 가운데 두가지는 좌우 반전만 되었을뿐 그 내부 구조는 같다.
따라서 4가지상황을 모두 고려할 필요없이 좌측 2개의 상황만 고려해서 경우의 수를 구한뒤 2배를 해주면 된다.
#1
이경우 나머지 6명이 악수하는 경우의 수가 되므로 dp[6] 이될것이다.
다음과정에서 이해하기 쉽게 dp[0]*dp[6]이라고 하자 (dp[0]은 0명이 악수하는 경우의 수 이므로 1)
#2
이경우 악수한 선 기준으로 좌측과 우측으로 보면
좌측은 2명이 악수하는경우 dp[2]
우측은 4명이 악수하는경우 dp[4]
이 둘이 독립이므로 dp[2]*dp[4]가 될것이다.
따라서 정리하면
dp[8] = ( dp[0]*dp[6] + dp[2]*dp[4] ) * 2
가 될것이다.
위 예시를 보면 8일때를 구하는데 2,4,6일때의 경우가 모두 쓰였다.
몇가지 경우를 더 살펴보면
dp[n]을 구할때 dp[n-2-k]*dp[k] + ... 의 꼴이 나오는것을 알수 있고
또한 n이 4의 배수일때는 위와같이 전체 구한경우의수에 2를 곱해서 최종 답을 도출해냈지만
그렇지않은 수 (10, 14, 18 등등.. ) 에서는 마지막 dp[(n-2)/2]*dp[(n-2)/2] 빼고 2배를 해야함을 알수있다.
n = int(input(""))
dp = [0] * 10001
dp[0] = 1
dp[2] = 1
dp[4] = 2
i = 6
while(i <= n):
total = 0
for j in range(i//4): # n이 4의 배수던 아니던 공통이다
j = j*2
total = total + dp[j]*dp[i-j-2]*2
if(i%4 == 2): # n이 4의 배수가 아닐때만 아래경우를 더해주어야한다
total = total + dp[(i-2)//2]*dp[(i-2)//2]
dp[i] = total%987654321
i = i+2
print(dp[n])
보통 점화식에서 n을 구할때 n-1이나 n-2까지만 고려하면 구할수 있었는데
이문제같은경우 n을 구할때 그 이전에 구했던 n-k들을 모두 이용했다는 점에서 조금 까다로웠다.
'알고리즘 > 백준' 카테고리의 다른 글
[알고리즘][8][백준_2515][C언어] - 전시장 (0) | 2020.02.24 |
---|---|
[알고리즘][7][백준_1648][Python3] - 격자판 채우기 (0) | 2020.02.06 |
[알고리즘][5][백준_1103][Python3] - 게임 (0) | 2020.02.02 |
[알고리즘][4][백준_2482][Python3] - 색상환 (0) | 2020.01.15 |
[알고리즘][3][백준_2228][Python3] - 구간 나누기 (0) | 2020.01.15 |