본문 바로가기

백준99

[python] 별꽃의 세레나데 (Easy) - 26217번 출력값이 하나로 정해지지 않고 범위에만 들어가면 정답으로 되는 확률 문제이다. 입력값에 따라 결과가 어떻게 나오는지 적어보면 간단한 일반화된 공식을 찾을 수 있다. 2 -> 2/2 + 2/1 = 3 96 -> 96/96 + 96/95 + ... + 96/1 = 494.08...... from fractions import Fraction n = int(input()) numerator = [n for _ in range(n)] denominator = [i for i in range(n,0,-1)] result = 0 for i in range(n): result+=Fraction(numerator[i],denominator[i]) print(float(result)) 2022. 12. 13.
눈 치우기 - 26215번 그리디로 해결하였다. while문을 이용한 무한루프로 눈을 효율적으로 치우는데 결과값이 1440을 넘어가는순간 break를 걸고 -1을 출력한다. 눈이 많이 쌓인 순서대로 정렬해준 뒤 효율적으로 눈을 치워주면 된다. n = int(input()) house=list(map(int,input().split())) house.sort() house = house[::-1] result = 0 while True: if result > 1440: result = -1 break if n>1: result+=house[1] house[0]-=house[1] house.pop(1) n-=1 if house[0] == 0: house.pop(0) n-=1 house.sort() house = house[::-1] .. 2022. 12. 12.
평범한 배낭 - 12865번 동적계획법으로 해결할 수 있는 문제이다. 배낭에 담을 물건을 쪼깨어 일부분만 담을 수 있다면 그리디로 풀 수 있지만, 그렇지 않기 때문에 동적계획법을 써줬다. 만약 가방의 무게가 20이고, 들어갈 수 있는 물건 5개가 다음과 같다면, 무게, 가치 2 3 3 4 4 8 5 8 9 10 동적계획법의 표현결과는 다음과 같다. n,k = map(int,input().split()) jewels=[[0,0]] for i in range(n): inn = list(map(int,input().split())) jewels.append(inn) dp = [[0]*(k+1) for i in range(n+1)] for gem in range(1, n+1): for bag_weight in range(1, k+1): i.. 2022. 12. 10.
출제비 재분배 - 26145번 출제자들이 돈을 받고 검수자들은 받지 못한다. 출제자들은 돈을 받고나서 나머지 모든 사람들에게 돈을 나눠준다. 각 사람들 수만큼 배열을 만들고, 들어가고 나오는 돈을 계산해준다. import sys n,m = map(int,input().split()) money = list(map(int,input().split())) total_money = [0 for _ in range(n+m)] for i in range(n): inn = list(map(int,sys.stdin.readline().split())) money[i] -= sum(inn) for j in range(n+m): total_money[j] += inn[j] for i in range(n): total_money[i] += money[.. 2022. 12. 10.
큐빙 - 5373번 빡구현 문제이다. 시간복잡도 생각 안하고 가장 단순한 방식으로 노가다로 풀었다. 50%에서 자꾸 틀렸는데, 2일동안 답을 찾기 위해 디버깅해본 결과 출력 시 join을 안해주었다. 출력 양식에 띄어쓰기를 포함하지 않고 딱 붙여서 출력해야한다. 직접 테스트 해볼 때, 만들어둔 show2함수와 https://rubiks-cube-solver.com/ko/에서 비교해보며 오답을 찾아내었다. 모든 오류를 확인해볼수 있는 반례는 1 12 F- R- U- B- L- D- F+ R+ U+ B+ L+ D+ 이다. 모든 면을 전개도처럼 펼쳐서 일일이 확인해보면 어디서 틀렸는지 확인할 수 있다. 위 반례의 답은 직접 구해보길 바란다. global up, front, right, left, back, down up = [[.. 2022. 12. 8.
Identify, Sort, Index, Solve - 26150번 람다식을 이용해 정렬해주는 것이 관건이다. import sys n = int(input()) arr = [] for _ in range(n): arr.append(list(sys.stdin.readline().split())) for i in range(n): arr[i][1] = int(arr[i][1]) arr.sort(key = lambda x:x[1]) for i in range(n): idx = int(arr[i][2]) print(arr[i][0][idx-1].upper(),end='') 2022. 12. 4.
케빈 베이컨의 6단계 법칙 - 1389번 플로이드 워셜 알고리즘으로 풀었다. 그래프에 친구들 간 관계의 비용을 계산한 후, 저장한다. 그래프에서 각 사람별로 친구들간 관계의 비용이 가장 낮은 사람을 구해준다. import sys from copy import deepcopy from math import inf n, m = map(int,input().split()) graph = [[inf]*n for _ in range(n)] for i in range(m): a,b = map(int,sys.stdin.readline().split()) graph[a-1][b-1] = 1 graph[b-1][a-1] = 1 def floyd(graph): d = deepcopy(graph) for a in range(n): for b in range(n):.. 2022. 11. 30.
경로 찾기 - 11403 플로이드 워셜 알고리즘으로 해결하였다. 마지막에 inf 인 것들은 0으로 바꿔주고 나머지들은 모두 1로 바꿔주고 출력하였다. import sys from copy import deepcopy from math import inf n = int(input()) graph = [[inf]*n for _ in range(n)] for i in range(n): inn = list(map(int,sys.stdin.readline().split())) for j in range(n): if inn[j]: graph[i][j] = 1 def floyd(graph): d = deepcopy(graph) for a in range(n): for b in range(n): for c in range(n): d[b][c].. 2022. 11. 30.
플로이드 - 11404번 동적 계획법 방식의 플로이드 워셜 알고리즘을 사용하는 문제이다. 그래프의 모든 정점에서 다른 정점들 까지의 최소 비용을 구해야한다. 갈 수 없는 곳은 math 모듈의 inf 무한대를 사용하여 표현해주고 마지막에 출력할 때 0으로 바꿔준다. 원본 그래프를 손상시키지 않기 위해 deepcopy를 사용했다. import sys from copy import deepcopy from math import inf n = int(input()) m = int(input()) graph = [[inf]*(n) for _ in range(n)] for i in range(m): a,b,c = map(int,sys.stdin.readline().split()) if graph[a-1][b-1]==inf: graph[a-.. 2022. 11. 29.
듣보잡 - 1764번 시간을 줄이기 위해 집합 자료형을 사용해준다. 마지막에 결과를 사전순으로 출력해야하기 때문에 리스트로 바꿔준 뒤, 출력해준다. import sys a,b = map(int,input().split()) arr=set() result=set() for _ in range(a): inn = sys.stdin.readline().strip() arr.add(inn) for _ in range(b): inn = sys.stdin.readline().strip() if inn in arr: result.add(inn) print(len(result)) result = list(result) result.sort() for i in result: print(i) 2022. 11. 14.
좌표 정렬하기 2 - 11651번 람다식을 통해 정렬 조건을 주었다. sort()에 key = lambda x:(x[1],x[0]) 를 주었다. 인덱스 1번, 인덱스 0번을 순서대로 정렬 우선순위를 부여하였다. t = int(input()) a = [] for _ in range(t): a.append(list(map(int,input().split()))) a.sort(key = lambda x:(x[1],x[0])) for i in a: print(i[0],i[1]) 2022. 11. 8.
제로 - 10773번 들어온 수를 스택에 담고 0이 들어오면 pop 해준다. from collections import deque import sys stack = deque() t = int(input()) for _ in range(t): inn = int(sys.stdin.readline()) if inn==0: if stack: stack.pop() else: stack.append(inn) print(sum(stack)) 2022. 11. 8.

티스토리툴바