DHistory

문제 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 """ 피보나치수열 d[n] = d[n - 1] + d[n - 2] """ n = int(input()) def solution(n): d = [0] * (10000 + 1) d[1] = d[2] = 1 for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] return d[n] print(solution(n)) 채점 결과

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 """ d[n]: 돈이 n원일 때 2원 짜리와 5원 짜리로 줄 수 있는 동전의 최소 개수 """ n = int(input()) INF = 987654321 def solution(n): if n == 1: return - 1 d = [INF] * (n + 1) d[2] = 1 for i in range(4, n + 1): if not i % 2: d[i] = min(d[i], i // 2) if not i % 5: d[i] = min(d[i], i // 5) d[i] = min(d[i], min(d[i - 2] + 1, d[i - 5] + 1)) return d[n] if..

문제 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 풀이 import sys def solution(note1, note2): note1 = sorted(note1) result = [] for target in note2: if binary_search(note1, target, 0, len(note1) - 1) != None: result.append(1) else: result.append(0) return result def binary_search(array, target, start, end): whi..

문제 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 풀이 import sys from collections import Counter n = int(sys.stdin.readline().rstrip()) cards = [] for _ in range(n): cards.append(int(sys.stdin.readline().rstrip())) def solution(cards): return sorted(Counter(cards).items(), key=lambda x: (-x[1], x[0]))[0][..

문제 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이 import sys from collections import Counter n = int(sys.stdin.readline().rstrip()) books = [] for _ in range(n): books.append(sys.stdin.readline().rstrip()) def solution(books): return sorted(Counter(books).items(), key=lambda x: (-x[1], x[0]))[0][0] ..

문제 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 """ 1. 국어 점수가 감소하는 순서로 2. 국어 점수가 같으면 영어 점수가 증가하는 순서로 3. 국어 / 영어점수가 같으면 수학 점수가 감소하는 순으로 4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 """ import sys n = int(sys.stdin.readline().rstrip()) scores = [] for _ in range(n): input = sys.stdin.readline().rstrip()..

문제 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 정렬과 이진 탐색으로 풀 수도 있지만 set을 이용하니 풀이가 깔끔하여 해당 방법으로 풀었다. import sys n, m = map(int, sys.stdin.readline().rstrip().split()) a = [] for _ in range(n): a.append(sys.stdin.readline().rstrip()) b = [] for _ in range(m): b.append(sys.stdin.readline().rstrip()) de..

문제 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) cards = list(map(int, sys.stdin.readline().rstrip().split())) m = int(sys.stdin.readline().rstrip()) numbers = list(map(int, sys.stdin.readline().rstrip().split())) def solution(cards, ..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) a = list(map(int, sys.stdin.readline().rstrip().split())) m = int(sys.stdin.readline().rstrip()) b = list(map(int, sys.stdin.readline().rstrip().split())) def solution(a, b): re..

문제 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 풀이 import sys text = sys.stdin.readline().rstrip() def solution(text): answer = [] for i in range(1, len(text)): for j in range(i + 1, len(text)): answer.append(text[0:i][::-1] + text[i:j][::-1] + text[j:len(text)][::-1]) return sorted(answer)[0] print(solut..