코딩89 [백준] 1656 - 랜선 자르기 (Python) 문제 출처: www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이: 나무 자르기 문제와 매우 흡사한 문제이다. 이진탐색으로 풀면 가능하다 이 문제에서는 target이 잘라야 하는 랜선 길이라고 두고 매번 갯수를 파악하면서 n개를 기준으로 right,left를 조정하면된다. k,n = map(int,input().split()) lans = [] for _ in range(k): lans.append(int(input())) .. 2021. 4. 2. [백준] 2805 - 나무 자르기(Python) 문제 출처: www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이: 이분탐색 문제이다. 아마도 이분 탐색인 문제를 파악하지 못하고 푼다면 시간초과를 마주하게 될 것이다. 필자는 아무리 생각해보아도 이분 탐색이 어떻게 적용되는지 모르겠어서 질문 게시판을 참조햇다 자르려는 높이를 x라고 하면, 그 때 잘라내는 나무의 양을 O(N)에 구할 수 있습니다. x가 작을 수록 나무의 양이 같거나 많아지는 것이 자명하므로, 높이.. 2021. 4. 2. [백준] 2869 - 달팽이는 올라가고 싶다 (Python) 문제 출처 : www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 풀이: 이 문제를 쉽게 생각하고 while문을 돌리면 무조건 시간초과가 난다. 입력값의 최대값이 1,000,000,000 이기 때문에) 이 문제에서 체크해야하는 부분은 "또, 정상에 올라간 후에는 미끄러지지 않는다." 라는 부분이다. 때문에 원하는 높이에 다 올라간 낮을 정답으로 출력해야 한다. 이를 수학적으로 표현하면 V_d (day 만큼 지났을때 있는 높이 ) = a * d - b * (d-1) 이를 d에 대해서 정리하면 day = v-b / a.. 2021. 4. 2. [백준] 2529 - 부등호 (Python) 문제 출처 : www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 문제 풀이 : 문제를 분할해서 생각해보자. 새로 추가되는 숫자에 대한 부등호 관계가 만족하는가? 새롭게 추가되는 숫자를 중복없이 어떻게 만들 것인가? 최소와 최대를 어떻게 구할 것인가? (따로 구분해주기) 위의 서브 문제들을 풀어가보자 새로운 숫자가 추가 될때 마다 앞에 숫자랑 비교해주는 함수를 만들자(check 함수) 백트래킹을 이용해보자. 숫자는 중복없이 0~9까지이므로 for문 돌려서 사용하면된다. 이때 .. 2021. 4. 2. 이전 1 2 3 4 5 ··· 23 다음 반응형
