본문 바로가기

프로그래밍

백준 4811 알약 - 파이썬 풀이 🦄 백준 4811 알약 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 4811 알약 - 파이썬 풀이 🦄 문제 DP를 이용해서, 알약을 먹는 경우의 수를 찾는 문제. Keypoints 나열하는 경우으 수를 생각한다. 총 2N개에서 중복으로 N개와 N개가 각각 있다. W가 H보다 앞서는 경우의 수를 생각하면 N+1 개로 나눠주면 된다. Solution import math while True : n = int(input()) if n==0: break numerator = math.factorial(2*n) denominator = (n+1)* math.factorial(n)**2 print(numerator//denominator) References Problem Link 더보기
백준 12865 평범한 배낭 - 파이썬 풀이 🦄 백준 12865 평범한 배낭 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 12865 평범한 배낭 - 파이썬 풀이 🦄 문제 DP를 이용해서, sob problem에 대한 해를 활용하는 문제이다. Keypoints Bigger problem : 주어진 N개의 물건에 대해서 모든 무게 W에 대한 가치를 최대화 한다. Smaller problem : 주어진 N-1개의 물건에 대해서 모든 무게 W에 대한 가치를 최대화 한다. 따라서 모든 무게에 대해서 가치의 최대값을 저장하고 새로운 물건(W, V)을 추가하면서 업데이트 하면 된다. Solution from sys import stdin as stdin N, MAXIMUM_VALUE = map(int, stdin.readli.. 더보기
백준 13460 구슬탈출 2 - 파이썬 풀이 🦄 백준 13460 구슬탈출 2 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 13460 구슬탈출 2 - 파이썬 풀이 🦄 문제 주어진 조건대로 구현 + BFS탐색을 하는 문제이다. Keypoints 구슬은 유동적으로 변하므로 Board에서 따로 제거해서 움직인다. 구슬은 두 개가 주어지며, 이동하는 방향에 따라서 먼저 움직이는 구슬이 있다. hole에 빠지게 되면, BFS를 도는 게 아니라, 종료해야 한다. Solution def move_up(board, red, blue, hole): if red[0] = blue[0]: first, second = red, blue else: first, second = blue, red fixed = first[1] for r i.. 더보기
[백준 14226 이모티콘] - 파이썬 풀이 🦄 백준 14226 이모티콘 문제해석 Key word 풀이 접근 Solution Try 1 Try 2 References 백준 14226 이모티콘 문제해석 초기상태로 화면에 1개의 이모티콘이 있다. 3가지 연산이 가능하다. 화면의 이모티콘 모두를 클립보드에 복사 후 덮어쓰기 클립보드의 이모티콘을 화면에 붙여넣기 화면의 이모티콘을 하나 제거하기 N개의 이모티콘을 화면에 남기기 위한 최소한의 연산 수를 구하는 문제 Key word 경우의 수 동적할당(?) 백트래킹 풀이 접근 경우의 수를 구하는 문제이므로, BFS로 경우의 수 트리를 탐색하는 문제로 생각한다. 모든 경우를 탐색하게 된다면, 시간 또는 메모리 초과가 나기 때문에 BackTracking으로 고려하지 않아도 되는 경우라면 빠르게 포기한다. Soluti.. 더보기
[백준 11052 카드 구매하기] - 파이썬 풀이 🦄 백준 11052 카드 구매하기 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 11052 카드 구매하기 - 파이썬 풀이 🦄 문제 N개의 카드 가격이 있을 때, N개를 지불하는데 사용되는 최대금액을 찾는 문제 Keypoints 1,2,3,4, ... 순서대로 DP에 최대값을 저장한다. K번째에서는 이중 for문의 index i에 대해서 합이 K= (i +K-i)이 되는 모든 i를 고려한다. Solution num_cards = int(input()) prices = list(map(int, input().split())) max_store_by_num = [p for p in prices] # 0 index is 1 number of card for i in range(.. 더보기
[백준 2688 줄어들지 않아] - 파이썬 풀이 🦄 백준 2688 줄어들지 않아 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 2688 줄어들지 않아 - 파이썬 풀이 🦄 문제 왼쪽의 Digit이 항상 오른쪽보다 작은 경우의 수를 찾는 문제이다. Keypoints 왼쪽의 수가 주어졌을 때, 오른쪽에 하나를 더 붙이는 수를 생각한다. XXX4 -> 4,5,6,7,8,9 6개를 붙일 수 있음. Solution def construct_dp(n): store_count = [[1 for i in range(10)]] for i in range(1,n): count_per_digit = [0 for i in range(10)] for digit in range(0, 10): count_per_digit[digit] = sum(.. 더보기
[백준 4811 알약] - 파이썬 풀이 🦄 백준 4811 알약 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 4811 알약 - 파이썬 풀이 🦄 문제 경우의 수를 구하는 문제이다. Keypoints $2N$ 길이의 수열이 있을 때, W,H에 의해서 절반이 중복되며, 구해야 하는 경우는, 왼쪽의 W의 갯수가 항상 H보다 많은 경우이다. Solution import math while True : n = int(input()) if n==0: break numerator = math.factorial(2*n) denominator = (n+1)* math.factorial(n)**2 print(numerator//denominator) References Problem Link 더보기
[백준 1446 지름길] - 파이썬 풀이 🦄 백준 1446 지름길 - 파이썬 풀이 🦄 문제 Keypoints Solution References 백준 1446 지름길 - 파이썬 풀이 🦄 문제 Shortest Path를 구현하는 문제이다. Keypoints 주어진 edge이외에, $i$ 번째 노드에서 $i+1$번째 노드로 갈 수 있으므로, edge가 존재한다. set을 이용하면, 다음에 갈 노드를 쉽게 보관할 수 있다. Solution import math def shortest_length(graph, start): distance = [math.inf for i in range(len(graph))] visited = [False for i in range(len(graph))] distance[start] = 0 visited[start] = .. 더보기

티스토리툴바