백준
-
[백준] 11899 괄호 끼워넣기 with PythonPS 2022. 3. 16. 18:06
📌 BOJ 11899 괄호 끼워넣기 💡 조건 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 문제. S의 길이는 1 이상 50 이하이며 불가능한 경우는 주어지지 않는다. 괄호열이란 여는 괄호 ‘(’와 닫는 괄호 ‘)’로만 구성된 문자열을 말합니다. 올바른 괄호열은 아래와 같이 정의할 수 있다. "()"는 올바른 괄호열입니다. A가 올바른 괄호열이라면 "(A)" 역시 올바른 괄호열입니다. A와 B가 모두 올바른 괄호열이라면 "AB" 역시 올바른 괄호열입니다. 문자열, 스택, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin g = stdin.readline().rstrip() cnt = 0 def solve(s): ..
-
[백준] 10166 관중석 with PythonPS 2022. 3. 16. 00:36
📌 BOJ 10166 관중석 💡 조건 반지름이 1인 원 위에는 좌석이 1개, 반지름이 2인 원 위에는 좌석이 2개, 이런 식으로 반지름이 D 인 원 위에는 좌석이 D 개가 있다. 무대에서 정확히 북쪽 방향에는 모든 원들에 좌석이 있으며, 하나의 원 위에 있는 좌석들은 동일한 간격을 두고 배치되어 있다. 공연에 반지름이 D1보다 같거나 크고, D2(D1 ≤ D2)보다 같거나 작은 원들에 배치된 좌석만을 활용하려고 한다. 좌석을 점으로 간주했을 때, 다른 좌석에 의해 무대 중심이 가려지는 좌석은 사용하지 않고, 그렇지 않은 좌석은 모두 사용한다. 숫자는 원의 반지름을 나타내고, ●은 공연에 사용되는 좌석, ⊗은 공연에 사용되지 않는 좌석을 나타낸다. 원의 반지름 D1과 D2가 양의 정수로 주어진다. 단, 1..
-
[백준] 5698 Tautogram with PythonPS 2022. 3. 16. 00:18
📌 BOJ 5698 Tautogram 💡 조건 Tautogram은 매우 특별한 형태의 두운법으로, 인접한 단어가 같은 글자로 시작하는 것을 말한다. 문장이 Tautogram이 되려면, 모든 단어가 같은 글자로 시작해야 한다. 선영이의 편지에 있는 문장이 주어졌을 때, Tautogram인지 아닌지 알아내는 프로그램을 작성하시오. 문장은 최대 50개의 단어로 이루어져 있으며, 공백으로 구분되어져 있다. 단어는 알파벳 대문자와 소문자로 이루어져 있고, 길이는 최대 20이다. 마지막 테스트 케이스의 다음 줄에는 '*'이 하나 주어진다. 입력으로 주어진 문장이 Tautogram이라면 'Y'를, 아니라면 'N'을 출력한다. 문자열 유형의 문제 🖥 소스 코드 from sys..
-
[백준] 3187 양치기 꿍 with PythonPS 2022. 3. 14. 23:23
📌 BOJ 3187 양치기 꿍 💡 조건 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹힌다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 몇마리의 양과 늑대가 남아있는가? 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다. 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250) BFS 유형의 문제 🖥 소스 코드 from collections import deque from sys import stdin board = [] n, m = ..
-
[백준] 2493 탑 with PythonPS 2022. 3. 14. 22:46
📌 BOJ 2493 탑 💡 조건 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 문제. N은 1 이상 500,000 이하 탑들의 높이는 1 이상 100,000,000 이하의 정수 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin..
-
[백준] 2096 내려가기 with PythonPS 2022. 3. 12. 02:29
📌 BOJ 2096 내려가기 💡 조건 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 최대 점수, 최소 점수를 구하는 프로그램을 작성하는 문제 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. 첫째 줄에 얻을 수..
-
[백준] 1531 투명 with PythonPS 2022. 3. 12. 02:20
📌 BOJ 1531 투명 💡 조건 세준이는 1×1크기의 그림으로 모자이크한 100×100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면 그림은 그 부분에서 보이게 된다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 왼쪽 아래 모서리의 x, y좌표, 오른쪽 위 모서리의 x, y좌표 순으로 주어진다. 모든 좌표는 100보다 작거나 같은 자연수이다. 시뮬레이션, 구현 🖥 소스 코드 from sys import stdin board = [[False] * 101 for _ in range(101)] n, m = map..
-
[백준] 1269 대칭 차집합 with PythonPS 2022. 3. 10. 18:09
📌 BOJ 1269 대칭 차집합 💡 조건 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다. 대칭 차집합의 원소의 개수를 출력하는 문제 해시맵, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.rea..
-
[백준] 12760 최후의 승자는 누구? with PythonPS 2022. 3. 10. 18:04
📌 BOJ 12760 최후의 승자는 누구? 💡 조건 최종 플레이어 N명이 남아있다. 각 플레이어는 M장씩의 숫자가 적힌 카드를 가지고 있으며, 이들은 매 턴 자신이 가진 카드 중 가장 큰 카드를 두고 비교를 하는데, 그 카드들 중 가장 큰 수를 가진 플레이어가 1점을 획득한다. 그 턴에 사용된 카드는 버리기로 한다. (가장 큰 수를 가진 플레이어는 여러 명일 수 있다.) 3. M번의 경기 후 가장 많은 점수를 획득한 플레이어는 몇 번 플레이어인지 구하는 문제. 2
-
[백준] 12018 Yonsei TOTO with PythonPS 2022. 3. 9. 23:28
📌 BOJ 12018 Yonsei TOTO 💡 조건 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다. 과목 수 n (1 ≤ n ≤ 100) 마일리지 m (1 ≤ m ≤ 100) 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. 정렬 유형의 문제 🖥 소..