본문 바로가기

코딩테스트19

[백준] 2437(저울) 파이썬 문제 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나.. 2021. 1. 27.
[백준] 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.