python
-
[백준] 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..
-
[백준] 12761 돌다리 with PythonPS 2022. 3. 23. 16:33
📌 BOJ 12761 돌다리 💡 조건 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A, B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배 나 B배의 위치로 이동을 할 수 있다. 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다. 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현..
-
[백준] 11104 Fridge of Your Dreams with PythonPS 2022. 3. 22. 17:22
📌 BOJ 11104 Fridge of Your Dreams 💡 조건 2진수를 읽어 10진수로 출력하는 문제 진수변환 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): print(int(stdin.readline().rstrip(), 2))🔖 예제 및 실행결과 예제 5 000000000000000000000001 000000000001010101010101 000000000000000000001010 101011001010101100101101 111111111111111111111111실행결과 1 5461 10 11316013 16777215⌨️ 문제 풀이 int() 함수를 사용해 2진수를 10진수로 출력해준다. in..
-
[백준] 10211 Maximum Subarray with PythonPS 2022. 3. 22. 17:03
📌 BOJ 10211 Maximum Subarray 💡 조건 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제) N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하는 문제. 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000) 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): n = int(stdin.read..
-
[백준] 8974 희주의 수학시험 with PythonPS 2022. 3. 21. 18:43
📌 BOJ 8974 희주의 수학시험 💡 조건 연습문제 중에 하나가 정수를 적어나가는 것이였는데 수열은 1이 한 개, 2가 두 개, 3이 세 개.. 와 같이 만들어진다. 이제 강민이는 희주에게 두 개의 정수 A, B를 부를텐데, 그럼 희주는 주어진 수열에서 A번째와 B번째 사이에 있는 모든 수들의 합을 말해야한다. 희주에게 문제를 내기 위해 정답을 계산하는 문제 사칙연산, 구현 유형의 문제 🖥 소스 코드 from sys import stdin arr, res = [], 0 a, b = map(int, stdin.readline().split()) for i in range(1, 50): cnt = 0 while cnt != i: arr.append(i) cnt += 1 for i in range(a, b ..
-
[백준] 8911 거북이 with PythonPS 2022. 3. 21. 18:32
📌 BOJ 8911 거북이 💡 조건 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다. F: 한 눈금 앞으로 B: 한 눈금 뒤로 L: 왼쪽으로 90도 회전 R: 오른쪽으로 90도 회전 L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 문제. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다. 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생..