알고리즘 정복하기!/백준 문제풀이 61

백준 1629번 Python / Math 문제 링크 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 시간 초과 풀이 a,b,c = map(int, input().split()) remainder = [] cal = a while True: tmp = cal % c if not tmp in remainder: remainder.append(cal % c) cal *= a else: break answer = remainder[b % len(remainder)] print(answer) 거듭제곱을 순차적으로 진행하면서, 나머지를 구합니다. 리스트에 해당.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 17.
백준 9237번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 풀이 n = int(input()) t = list(map(int, input().split())) t.sort(reverse=True) answer = 1 + t[0] + 1 for i in range(1, len(t)): if 1 + i + t[i] + 1 > answer: answer = 1 + i + t[i] + 1 print(answer) 묘목을 빠르.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 16.
백준 1676번 Python / Math 문제 링크 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 n = int(input()) cal = 1 for i in range(1, n+1): cal = cal*i arr = list(str(cal)) cnt = 0 for i in range(len(arr)-1, 0, -1): if arr[i] == '0': cnt+=1 else : break print(cnt) 먼저, for문을 통해 팩토리얼 계산을 수행했습니다. 그리고 결괏값을 문자열로 바꾸어 리스트에 하나하나씩 저장했습니다. 마지막으로, for문으로 역순으로 순회를.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 16.
백준 2748번 Python / Dynamic Programming 문제 링크 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 n = int(input()) fibo = [0, 1] answer=0 for _ in range(n-1): answer = fibo[0] + fibo[1] fibo[0] = fibo[1] fibo[1] = answer if n==1: print(1) else: print(answer) 처음 fibo라는 리스트에 0, 1을 선언하고 피보나치 방식.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 14.
백준 5545번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/5545 5545번: 최고의 피자 첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄 www.acmicpc.net 풀이 n = int(input()) a,b = map(int, input().split()) c = int(input()) d = [] for _ in range(n): d.append(int(input())) d.sort(reverse=True) compare_kcal = c/a total_price = a total_kcal = c cnt.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 13.
백준 1010번 Python / Math 문제 링크 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 시간 초과 풀이 import itertools t = int(input()) for _ in range(t): n, m = map(int, input().split()) print(len(list(itertools.combinations(range(m),n)))) 정답 풀이 import math t = int(input()) for _ in range(t): n, m = map(i.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 12.
백준 11653번 Python / Math 문제 링크 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 n = int(input()) for i in range (2, n+1): while n % i == 0: n = n // i print(i) 처음엔 math.sqrt()를 사용해 주어진 수의 제곱근의 범위만큼만 반복하려다가 제출한 것처럼 돌려도 시간초과가 나오지는 않을 것 같아서 위와 같이 해결했습니다. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 12.
백준 9613번 Python / Math 문제 링크 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 import math t = int(input()) answer=0 for _ in range(t): data = input().split() del data[0] for i in range(len(data)-1): cnt = len(data) for j in range(cnt): if i < j: answer += math.gcd(int(data[i]), .. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.

티스토리툴바