python
-
[백준] 1660 캡틴 이다솜 with PythonPS 2022. 3. 6. 01:17
📌 BOJ 1660 캡틴 이다솜 💡 조건 N은 300,000보다 작거나 같은 자연수이다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하는 문제 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] num = 0 i = 1 while n > num: num += (i * (i + 1)) // 2 arr.append(num) i += 1 dp = [int(1e9) for i in range(n + 1)] for i ..
-
[백준] 1755 숫자놀이 with PythonPS 2022. 3. 6. 00:49
📌 BOJ 1755 숫자놀이 💡 조건 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다. 문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것. M 이상 N 이하의 정수를 문제 조건에 맞게 정렬하여 한 줄에 10개씩 출력한다. 정렬 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] num = 0 i = 1 while n ..
-
[백준] 16935 배열 돌리기 3 with PythonPS 2022. 3. 4. 21:40
📌 BOJ 16935 배열 돌리기 3 💡 조건 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 1번 연산은 배열을 상하 반전시키는 연산이다. 2번 연산은 배열을 좌우 반전시키는 연산이다. 3번 연산은 오른쪽으로 90도 회전시키는 연산이다. 4번 연산은 왼쪽으로 90도 회전시키는 연산이다. 5, 6번은 문제 참고 첫째 줄에 배열의 크기 N, M과 수행해야 하는 연산의 수 R이 주어진다. 2 ≤ N, M ≤ 100, N, M은 짝수 1 ≤ R ≤ 1,000 둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다. 1 ≤ Aij ≤ 108 연산은 공백으로 구분되어져 있고, 문제에서 설명한 연산 번호이며, 순서대로 적용시켜야 한다. 구현 유형의 문제 🖥 소스 코드 from sys im..
-
[백준] 15965 K번째 소수 with PythonPS 2022. 3. 4. 21:29
📌 BOJ 15965 K번째 소수 💡 조건 서브태스크가 존재한다. 2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다. 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) k번째 소수를 구하는 문제 수학, 에라토스테네스의 체 유형의 문제 🖥 소스 코드 BIG_NUM = 10**7 k = int(input()) array = [1 for _ in range(BIG_NUM + 1)] answer = [] for i in range(2, BIG_NUM + 1): if array[i]: answer.append(i) for j in range(i+i, BIG_NUM + 1, i): array[j] = 0 print(answer[k - 1]) 🔖 예제 및 실행결과 ..
-
[백준] 10384 팬그램 with PythonPS 2022. 3. 3. 19:20
📌 BOJ 10384 팬그램 💡 조건 팬그램은 모든 알파벳을 적어도 한 번씩을 사용한 영어 문장을 말한다. 더블 팬그램은 모든 알파벳을 적어도 두 번씩은 사용한 문장을 말하고, 트리플 팬그램은 모든 알파벳을 적어도 세 번씩은 사용한 문장을 말한다. 입력은 여러 줄의 테스트케이스들로 이루어진다. 첫째 줄에 테스트케이스의 수 n이 주어진다. 각 테스트케이스는 영어 소문자와 대문자, 특수기호들로 이루어진다. 팬그램이 아닐 경우 - Not a pangram 팬그램일 경우 - Pangram! 더블 팬그램일 경우 - Double pangram!! 트리플 팬그램일 경우 - Triple pangram!!! 구현 유형의 문제 🖥 소스 코드 from sys import stdin for i in range(1, int(s..
-
[백준] 9742 순열 with PythonPS 2022. 3. 3. 19:08
📌 BOJ 9742 순열 💡 조건 집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하는 문제 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin from math import factorial def solve(string..
-
[백준] 8394 악수 with PythonPS 2022. 3. 2. 23:53
📌 BOJ 8394 악수 💡 조건 회의가 끝났고, 이제 악수를 하는 시간이다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다. 자리를 벗어나지 않고 악수를 하는 방법의 수를 구하는 문제 각 사람들은 자신의 왼쪽이나 오른쪽에 있는 사람들과 악수를 할 수 있다. (안 할 수도 있다) 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. 수가 매우 커질 수 있기 때문에, 마지막 자리만 출력한다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [0 for _ in range(n + 1)] arr[0], arr[1] = 1, 1 for i in range(2, n + 1): ar..
-
[백준] 6443 애너그램 with PythonPS 2022. 3. 2. 23:42
📌 BOJ 6443 애너그램 💡 조건 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin def solve(l, s): if l == 0: visited.add(s) return for i in range(26..
-
[백준] 2697 다음수 구하기 with PythonPS 2022. 3. 1. 22:59
📌 BOJ 2697 다음수 구하기 💡 조건 A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수. A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때. 첫째 줄에 테스트 케이스의 개수 T(1 data[idx]: a.append(b.pop(i)) a.extend(b) break print(''.join(map(str, a)))🔖 예제 및 실행결과 예제 3 123 279134399742 987실행결과 132 279134423799 BIGGEST⌨️ 문제 풀이 입력받은 숫자를 역순으로 탐색합니다. 왼쪽에 있는 값이 오른쪽보다 작아질 경우, idx에 해당 인덱스 값을 넣어줍니다. 숫자를 a 와 b 로 나누는데..
-
[백준] 1855 암호 with PythonPS 2022. 3. 1. 22:42
📌 BOJ 1855 암호 💡 조건 먼저 암호화 할 문자열을 1,1부터 위에서 아래 순서대로 채운다. 그리고 가장 밑의 행을 채운 후에는 오른쪽 열에서 다시 같은 과정을 반복한다. 암호화 된 문자열과 몇 개의 열로 암호화를 하였는지 주어져 있을 때 원래의 문자열을 구하는 프로그램을 작성하는 문제. 열의 개수 K(1 ≤ K ≤ 20)가 주어진다. 두 번째 줄에는 암호화 된 문자열(모두 영소문자)이 주어진다. (문자열의 길이는 200 이하이며 K의 배수이다.) 구현, 문자열 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) s = stdin.readline().rstrip() arr = [] for i in range(0, len(s), n): a..