[브론즈 2] 백준 1297 - TV 크기 (파이썬)
[브론즈 2] 백준 1297 - TV 크기 (파이썬)
2025.09.09https://www.acmicpc.net/problem/1297이 문제는 TV 대각선 길이 D와 높이, 너비의 비율 H:W 가 주어진다.실제 TV의 높이와 너비 (h, w)는 피타고라스 정리로 표현할 수 있다.여기서는 비율 관계가 성립한다. 아래 수식을 참고하자.즉, 실제 높이와 너비는 H와 W를 일정 비율로 확대한 값이다.사칙연산으로 접근하면 높이와 너비를 K배 만큼 확대한 값이라고 한다면, 다음과 같이 수식을 새울수 있다.흔히 아는 대각선 공식에 대입하면 필요한 수식은 다음과 같다.작성한 코드는 다음과 같다.# 백준 1297 - TV 크기import mathD, H, W = map(int, input().split())R = D / (H ** 2 + W ** 2) ** 0.5print(int(H *..
[실버 3] 백준 6666 - Help Me with the Game (파이썬)
[실버 3] 백준 6666 - Help Me with the Game (파이썬)
2025.07.31분류 : 구현링크 : https://www.acmicpc.net/problem/6666풀이문제집에서 이거 안풀면 꿈에서 나온다는 말이 있어서 찾아보게된 문제이며, 문제 번호부터가 6666으로 예사롭지가 않다.근데 진짜 문제도 예사롭지 않다.입력을 한번 봐보자+---+---+---+---+---+---+---+---+|.r.|:::|.b.|:q:|.k.|:::|.n.|:r:|+---+---+---+---+---+---+---+---+|:p:|.p.|:p:|.p.|:p:|.p.|:::|.p.|+---+---+---+---+---+---+---+---+|...|:::|.n.|:::|...|:::|...|:p:|+---+---+---+---+---+---+---+---+|:::|...|:::|...|:::|....
[실버 2] 백준 11279 - 최대 힙 (파이썬)
[실버 2] 백준 11279 - 최대 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/11279풀이백준 1927과 비슷한 문제이다. 1927 최소 힙 문제에서는 정석대로 heap에 값을 양수로 넣었지만, 이번 문제는 최대 힙을 구하는 문제이기에, -를 붙여서 음수로 넣어주면 힙에서는 최대 힙으로 정렬되게 된다.이때 문제점은 pop 할때도 음수로 나오기에, 다시한번 -를 붙여주면, 최대 힙으로 출력 할 수 있다.코드# 백준 11729 - 최대 힙import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = []for i in range(N) : x = int(input()) if x == 0 : if len(heap) > ..
[실버 2] 백준 1927 - 최소 힙 (파이썬)
[실버 2] 백준 1927 - 최소 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/1927풀이힙의 기초적인 문제이다. 사실 시간초과가 나긴했는데, sys.stdin.readline을 고려하지 못했다.문제에서는 N이 최대 10만개이기 때문에 단순히 input()으로만으로는 당연히 시간 초과가 날 수 밖에 없다.문제에서 N을 입력받고, 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 X가 주어진다고 한다.X가 0이 아닌 경우에는 배열에 자연수 X를 넣고, 0이라면 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하면 된다.이에 적합한 자료구조는 heap이기에 아래와 같은 코드로 작성하였다.코드# 백준 1927 - 최소 힙import heapqimport sysinput = sys.stdin.r..
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
2025.07.17분류 : 브루트포스 + 자료구조링크 : https://www.acmicpc.net/problem/11578풀이1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.A = [list(map(int, input().split()))[1:] for _ in range(M)]A = [set(a) for a in A]각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.set(a)로 변환해서 나중에 합집한 연산을 쉽게 ..
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
2025.07.11https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..
[골드 5] 백준 2591 - 숫자카드 (파이썬)
[골드 5] 백준 2591 - 숫자카드 (파이썬)
2025.06.20https://www.acmicpc.net/problem/2591풀이34까지의 숫자 카드가 있을 때, 주어진 숫자 문자열 S를 한 자리 또는 두 자리 숫자로 쪼개어 카드 조합을 만드는 방법의 수를 구하는 문제이다. 단, 앞자리가 0이면 안 되고, 두 자리 수는 134 사이의 유효한 카드 번호여야 한다.D[i]: 문자열 S의 앞에서 i자리까지 만들 수 있는 카드 조합 수점화식한 자리 수 (S[i-1])가 '0'이 아니면 D[i] += D[i-1]두 자리 수 (S[i-2:i])가 '10' ~ '34' 범위에 속하면 D[i] += D[i-2]S = input()D = [0] * (len(S) + 1) # D[0] ~ D[len(S)]D[0] = 1 # 빈 문자열은 1가지 방법 (기저 조건)for i in ..
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
2025.04.16https://www.acmicpc.net/problem/1038풀이감소하는 수란 각 자릿수가 왼쪽부터 오른쪽으로 감소하는 수이다.예를 들어서, 321, 740, 1 , 20 이런식을 의미한다.0부터 9876543210 까지 총 1023개의 감소하는 수가 존재한 다는것을 알 수 있다.입력 N이 주어졌을때, N번째 감소하는 수를 출력하는 문제이다.만약 존재하지 않으면 -1을 출력해야 한다.for i in range(1, 11): for combination in combinations(list(range(10)), i):combinations(range(10), i)는 0~9중 i개를 뽑는 조합을 구한다예를 들어서 i 가 2라면 (0, 1), (0, 2), … , (8, 9)와 같은 모든 조합이 나온..
백준 31962 - 등교 (파이썬)
백준 31962 - 등교 (파이썬)
2025.03.26https://www.acmicpc.net/problem/31962풀이학생 N명이 학교 까지 가는데 S[i] 분이 걸리고, 등교 준비 시간으로 T[i]분이 필요하다.등교 마감 시간 X분 전에 도착해야한다.이때 등교 가능한 학생 중 등교 시간이 가장 오래 걸리는 학생의 등교 시간(S[i])를 구하는 문제이다.단, 어떤 학생도 등교할 수 없다면 -1을 출력해야한다.즉, 각 학생에 대해서 S[i] + T[i]의 값이 X 보다 작거나 같음을 만족하면, max_time을 업데이트 하는 방식으로 풀수 있다.코드# 백준 31962 - 등교# 분류 : 구현N, X = map(int, input().split())S = [0] * NT = [0] * Nfor i in range(N) : S[i], T[i] = ma..
백준 11726 - 2 x n 타일링 (파이썬)
백준 11726 - 2 x n 타일링 (파이썬)
2025.02.21분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/11726풀이점화식을 새워야 한다. 일단 An : 2 * n 타일을 1 * 2, 2 * 1 타일로 채우는 경우의 수를 생각해야한다.An = A(n - 1) + A(n - 2) 라는 점화식을 세울 수 있다.즉 이 문제를 생각해 보면, 숫자가 너무 커지기 때문에 일단 10007로 나눈다는 조건을 생각해야한다.먼저 dp 배열에 들어갈 초기 값을 생각한다.1번의 dp는 2 * 1 타일에 들어 갈수 있는 타일은 1개이다.2번의 dp는 2 * 2 타일에 들어 갈 수 있는 타일은 총 2개이다.1 * 2 타일 2개인 방법 1개2 * 1 타일 2개인 방법 1개예시를 생각해보자, 2 * 5 크기의 직사각형을 채운 한 가지 방법의 예를 확인..