목록정상회담2 (1)

프로그래밍에 대한 고찰 및 생각

[알고리즘][6][백준_1670][Python3] - 정상 회담 2

문제 이해 문제자체는 간단하지만 n이 조금만 커져도 경우의수가 커지고 점화식도 쉽게 발견되지 않아 조금은 까다로웠던 문제였다. 서로 팔이 교차하지 않는 것을 중점으로 생각해봐야 할것같다. 알고리즘 전략 점화식에 접근할때 n이 주어졌을때 그 상황들을 분해하려고 고민을 했다. 먼저 n = 8 일때로 먼저 분석을 해보자. ( 편의상 n=k일때 가능한 경우의 수를 dp[k]라고 하자 ) 이 상황에서 악수를 할수 있는 경우의 수를 찾다보면 한가지 규칙을 찾을 수 있다. 어떤사람과 어떤사람이 악수할때 그 둘 사이에 있는 사람의 수가 홀수가 되면 안된다는 것이다. 따라서 파란색 점을 기준으로 할때 이 사람이 악수 할수 있는 사람은 위의 3점과 자신을 제외한 4개의 점이다. 파란색이 악수 할수있는 점은 다음과 같다. ..
알고리즘/백준 2020. 2. 6. 11:34
이전 Prev 1 Next 다음