브루트포스
-
[백준] 10419 지각 with PythonPS 2023. 4. 3. 16:14
📌 BOJ 10419 지각 💡 조건 교수님의 지각시간 0이상의 정수 t와 수업을 일찍 마쳐주는 시간 s 사이에는 s = t**2 의 관계가 있다. 창영이가 궁금한 경우의 수 T(1 ≤ T ≤ 100)가 첫 번째 줄에 주어지고, 이어서 T 개의 줄에 수업시간 d(1 ≤ d ≤ 10,000, d는 정수)가 차례대로 주어진다. 수업시간에 따른 교수님이 지각할 수 있는 최대 시간 t를 정수로 구해서 출력한다. 지각할 수 있는 최대의 시간을 알아보는 문제 브루트포스 유형의 문제 🔖 예제 및 실행결과 예제 1 5 1 2 5 6 7 실행결과 1 0 1 1 2 2 ⌨️ 문제 풀이 지각할 수 있는 최대시간을 구하려면, 수업시간 d의 최대값이 얼마인지 확인해봐야한다. 지각할 수 있는 최대시간은 100부터 -1씩 줄여나가 ..
-
[백준] 1057 토너먼트 with PythonPS 2022. 6. 5. 16:24
📌 BOJ 1057 토너먼트 💡 조건 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고..
-
[백준] 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..
-
[백준] 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..
-
[백준] 5671 호텔 방 번호 with PythonPS 2022. 3. 18. 18:06
📌 BOJ 5671 호텔 방 번호 💡 조건 선영이는 투숙객에게 불운이 찾아오는 것을 피하기 위해서 반복되는 숫자가 없게 방 번호를 만들려고 한다. 정부는 선영이의 호텔 방 번호는 N보다 크거나 같고, M보다 작거나 같아야 한다는 조건을 걸고 신축 허가를 내주었다. 선영이의 새 호텔에는 방이 최대 몇 개 있을 수 있을까? 두 방이 같은 방 번호를 사용할 수 없다 입력은 여러 개의 테스트 케이스로 이루어져 있고, 한 줄이다. 각 줄에는 문제의 설명에 나와있는 N과 M이 주어진다. (1 ≤ N ≤ M ≤ 5000) 각각의 테스트 케이스에 대해서 N보다 크거나 같고, M보다 작거나 같은 수 중에서 반복되는 숫자가 없는 것의 개수를 출력한다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys impo..
-
[백준] 1342 행운의 문자열 with PythonPS 2022. 3. 1. 03:58
📌 BOJ 1342 행운의 문자열 💡 조건 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin arr = stdin.readline().rstrip() cnt = 0 point = [0 for _ in range(26)] for i in arr: point[ord(i) - 97] += 1..
-
[백준] 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..