백준
-
[백준] 10546 배부른 마라토너 with PythonPS 2022. 2. 24. 18:13
📌 BOJ 10546 배부른 마라토너 💡 조건 참가자 수 N이 주어진다. (1 ≤ N ≤ 105) N개의 줄에는 참가자의 이름이 주어진다. N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다. 참가자들 중엔 동명이인이 있을 수도 있다. 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까? 해시맵 자료구조 응용 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) mara_tang = {} for _ in range(n): name = stdin.readline().rstrip() if name not in ..
-
[백준] 9372 상근이의 여행 with PythonPS 2022. 2. 22. 20:17
📌 BOJ 9372 상근이의 여행 💡 조건 N개국을 여행할 상근이에게 가장 적은 비행기를 타고 여행할 수 있게 도와주자. 테스트 케이스의 수 T(T ≤ 100) 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 그래프이론, 유니온-파인드 유형의 문제 🖥 소스 코드 from sys import stdin def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, paren..
-
[백준] 2628 종이 자르기 with PythonPS 2022. 2. 22. 20:01
📌 BOJ 2628 종이 자르기 💡 조건 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램 정렬 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin..
-
[백준] 2168 터널 위의 대각선 with PythonPS 2022. 2. 21. 17:23
📌 BOJ 2168 터널 위의 대각선 💡 조건 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 문제. x와 y는 1,000,000,000 이하의 자연수 수학, 정수론, 유클리드 호제법유형의 문제 🖥 소스 코드 from sys import stdin from math import gcd x, y = map(int, stdin.readline().split()) print(x + y - gcd(x, y))🔖 예제 및 실행결과 예제 ..
-
[백준] 2075 N번째 큰 수 with PythonPS 2022. 2. 21. 17:05
📌 BOJ 2075 N번째 큰 수 💡 조건 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 표에 채워진 수는 모두 다르다. N(1 ≤ N ≤ 1,500) 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 자료구조 응용, 우선순위 큐 활용, 정렬 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n = int(stdin.readline()) q = [] cnt = 0 for _ in range(n): data = list(map(int, stdin.readline().split())) for j in data: if cnt != n: heapq.heap..
-
[백준] 15970 화살표 그리기 with PythonPS 2022. 2. 20. 23:01
📌 BOJ 15970 화살표 그리기 💡 조건 부분 점수가 있는 문제. 점들의 개수를 나타내는 정수 N N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다. 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 문제. 각 점은 N개의 색깔 중 하나를 가진다. 각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다. 브루트포스유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] for _ in range(n): x, y = m..
-
[백준] 13565 침투 with PythonPS 2022. 2. 19. 18:10
📌 BOJ 13565 침투 💡 조건 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다. 맨 윗줄에서 받은 전기가 맨 밑 줄까지 갈 수 있다면 True, 아니면 False BFS 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.readline().split()) board = [] visited = set() for _ in range(n): board.append(list(map(int, list(stdin.readl..
-
[백준] 11048 이동하기 with PythonPS 2022. 2. 19. 17:59
📌 BOJ 11048 이동하기 💡 조건 N×M 크기의 미로 (1 ≤ N, M ≤ 1,000) (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동가능. 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하는 문제 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = [] candy = [[0] * m for _ in range(n)] res = 0 for _ in ..
-
[백준] 2477 참외밭 with PythonPS 2022. 2. 14. 18:20
📌 BOJ 2477 참외밭 💡 조건 m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20) 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 구현 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) nums = [] x, y = [], [] for _ in range(6): direction, length = map(int, stdin.rea..