백준
-
[백준] 14562 태권왕 with PythonPS 2022. 5. 12. 01:26
📌 BOJ 14562 태권왕 💡 조건 테스트 케이스의 수 C(1 ≤ C ≤ 100) 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) 태균이가 현재 할 수 있는 연속 발차기는 두가지가 있다. A는 현재 점수만큼 점수를 얻을 수 있는 엄청난 연속 발차기이다. 하지만 상대 역시 3점을 득점하는 위험이 있다. B는 1점을 얻는 연속 발차기이다. 태균이의 점수 S와 상대의 점수 T가 주어질 때, S와 T가 같아지는 최소 연속 발차기 횟수를 구하는 문제 BFS(너비우선탐색) 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque def solve(s, t): q = deque() q.append((0, s, t)) ..
-
[백준] 16926 배열 돌리기 1 with PythonPS 2022. 5. 11. 16:01
📌 BOJ 16926 배열 돌리기 1 💡 조건 크기가 N×M인 배열이 있을 때, 배열을 반시계 방향으로 돌린다. 첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다. 둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다. 2 ≤ N, M ≤ 300 1 ≤ R ≤ 1,000 min(N, M) mod 2 = 0 1 ≤ Aij ≤ 108 배열을 R번 회전시킨 결과를 출력하는 문제 구현 유형의 문제 🖥 소스 코드 from sys import stdin n, m, r = map(int, stdin.readline().split()) arr = [] for i in range(n): arr.append(list(map(int, stdin.readline().split()))) for _ ..
-
[백준] 14696 딱지놀이 with PythonPS 2022. 5. 11. 15:57
📌 BOJ 14696 딱지놀이 💡 조건 4, 3, 2, 1 에 해당하는 숫자가 각 몇 개인지 파악하여 승자가 누구인지 출력하는 문제 서브태크스가 존재한다. 출력의 i번째 (1 ≤ i ≤ N) 줄에 정확히 한 글자를 출력하는데, 출력하는 글자는 A, B, D 중 하나로 라운드 i의 결과를 나타낸다. 각 라운드의 결과는 A가 승자라면 A, B가 승자라면 B, 무승부라면 D이다. 구현 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): a = list(map(int, stdin.readline().split()))[1:] b = list(map(int, stdin.readline().split()))[1:] _4a, _4b =..
-
[백준] 12970 AB with PythonPS 2022. 5. 9. 20:52
📌 BOJ 12970 AB 💡 조건 문자열의 길이 n 0 ≤ i < j < N 이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍의 개수 K 개가 있다. N과 K가 주어진다. (2 ≤ N ≤ 50, 0 ≤ K ≤ N(N-1)/2) 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. S가 존재하지 않는 경우에는 -1을 출력한다. 수학, 그리디 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin n, k = map(int, stdin.readline().split()) def solve(n, k): s = list('B' * n) acnt, curk, lidx = 0, ..
-
[백준] 11508 2+1 세일 with PythonPS 2022. 5. 9. 20:35
📌 BOJ 11508 2+1 세일 💡 조건 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다. 유제품의 수 N (1 ≤ N ≤ 100,000) N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000) 정답은 231-1보다 작거나 같다. 최소비용으로 유제품을 구입할 수 있도록 도와주는 문제. 그리디, 정렬 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin arr = [] n = int(stdin.readline()) for i in range(n): arr.append(int(stdin.readline())) arr.sort(re..
-
[백준] 2302 극장 좌석 with PythonPS 2022. 3. 31. 04:31
📌 BOJ 2302 극장 좌석 💡 조건 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다. 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. 방법의 가짓수는 2,..
-
[백준] 2012 등수 매기기 with PythonPS 2022. 3. 31. 04:13
📌 BOJ 2012 등수 매기기 💡 조건 2007년 KOI에 N명의 학생들이 참가하였다. 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. 1등부터 N등까지 동석차 없이 등수를 매겨야한다. 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다. 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. 그리디알고리즘,..
-
[백준] 1343 폴리오미노 with PythonPS 2022. 3. 29. 17:04
📌 BOJ 1343 폴리오미노 💡 조건 AAAA와 BB 폴리오미노 2개를 무한개만큼 가지고 있다. '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 문제 보드판의 크기는 최대 50이다. 문자열 유형의 문제 🖥 소스 코드 from sys import stdin p = stdin.readline().rstrip() p = p.replace('XXXX', 'AAAA') p = p.replace('XX', 'BB') if 'X' in p: pri..
-
[백준] 1145 적어도 대부분의 배수 with PythonPS 2022. 3. 29. 16:56
📌 BOJ 1145 적어도 대부분의 배수 💡 조건 다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다. 서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 문제 100보다 작거나 같은 자연수이고, 서로 다른 수이다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from math import lcm arr = list(map(int, stdin.readline().split())) res = int(1e9) for i in range(5): for j in range(i + 1, 5): for k in range(j + 1, 5): res = min(res, lcm(arr[..
-
[백준] 1038 감소하는 수 with PythonPS 2022. 3. 23. 17:16
📌 BOJ 1038 감소하는 수 💡 조건 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. N번째 감소하는 수를 출력하는 문제. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 백트래킹, 브루트포스 유형의 문제 🖥 소스 코드 from sys import stdin dp = [x for x in range(10)] def solve(cnt, s, num): if cnt == len(s): dp.append(int(s)) return for i in range(num, -1, -1): if not s: solve(cnt, s..