https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Dynamic Programming (DP) 다이나믹 프로그래밍은 하나의 큰 문제를 나눴을 때 생기는 작은 문제들 즉, subproblem들 중 중복되는 subproblem들의 값들을 메모리에 저장(memoization)하여 같은 문제를 반복해서 푸는 비효율적인 계산을 줄이고자 한다. 그렇기 때문에 풀었던 subproblem이 또 나왔을 때, 그 문제를 다시 풀 필요 없이 이전에 저장해뒀던 값을 찾아가면 된다. 다이나믹 프로그래밍은 크게 Bottom-Up과 Top-Down 방식으로 나뉜다. 1. Top-Down..
https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net First Try 1 import time import math start = time.time() n, k = map(int, input().split()) result = 1 for i in range(k): result *= n-i result /= math.factorial(k) print(int(result)) finish = time.time() print(f'time: {round(finish-start,3)}') >>> 10 >>> time: 3.205 Fi..
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net First Try """ 최대공약수 : 교집합 최소공배수 : 합집합 """ def get_factors(x: int) -> list: """ 입력받은 x의 약수를 반환한다. """ factors = [] n = 2 while (True): if x == 1: break if x % n == 0: factors.append(n) x = x / n else: n += 1 return factors def get_gcn(a, b: list): """ 두 수의 약수 리스..
https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net First Try n = int(input()) # 후보 수를 입력받는다. candidates = [[i,int(input())] for i in range(n)] # (기호번호, 득표수) 형태로 리스트에 저장. dasom = candidates[0][1] # 다솜의 득표수를 따로 저장해둔다. cnt = 0 # 다솜이 타 후보자의 투표자를 매수한 횟수 while (True): candi..
https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net First Try scenario = 0 students = [] while (True): scenario += 1 n = int(input()) if n == 0: break name = [] for _ in range(n): name.append(input()) records = [0]*n for _ in range((2*n)-1): records[int(input()[0])-1] += 1 ..
https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net First Try board = input() n = 0 result = "" for w in board: if w=="X": n += 1 else: if n % 2 == 0: result += (("AAAA")*(n//4) + ("B")*(n%4) n = 0 result += "." else: result = -1 break if n==len(board): if n % 2 == 0: result += (("AAAA")*(n//4) + ("B")*(n%4)) else: result = -1 print..
https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net First Try word = input() #변수 word에 단어를 입력받는다. std1 = word.index(sorted(word)[0]) #알파벳순으로 word를 sort하여 가장 앞쪽 문자를 std1에 저장한다. std2 = word.index(sorted(word)[1]) #그 다음에 있는 문자를 저장한다. #문제의 조건 중 "이렇게 만들어진 단어들 중, 가장 앞서는 단어를 출력"이 있다..
https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net First Try n = int(input()) spec = [] for i in range(n): w, h = input().split() spec.append((i, w, h)) #weight = sorted(spec, key=lambda x: x[1], reverse=True) weight = sorted(spec, key=lambda x: (x[1], x[2]), reverse..