코딩테스트10 [백준] 1697(숨바꼭질) 파이썬 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 풀이 및 리뷰 전형적인 BFS 문제이므로 풀이는 크게 어렵지 않다. .. 2021. 1. 5. [백준] 11726(2XN 타일링) C++ 처음엔 DP 방식이아닌 조합(combination)을 이용한 공식을 사용하여 풀려고 시도했다 n이 1000인 경우 1000C0 + 999C1 + ... + 501C499 + 500C500 이런 식이 나오는데 당연히 시간초과가 나와버렸다 combination의 시간을 줄이는 알고리즘을 찾아보고 생각해봤지만 해결할 수가 없어서 DP 방식을 다시 생각해 봤다 다른 사람의 코드를보니 P(n) = P(n-1) + P(n-2)란 점화식이 나왔더라..이 간단한게 왜 안 보였는지... 그리고 문제에선 해당 경우의 수를 10,007로 나눈 나머지를 출력하란다 당연히 n에 대한 경우의 수를 구한다음에 10,007로 나눈 나머지를 출력했는데 범위를 초과해버린다 아마 unsigned long long 을 써도 초과하는 듯 한.. 2020. 8. 31. 이전 1 2 3 다음
