코딩테스트
-
[백준] 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씩 줄여나가 ..
-
[백준] 5692 팩토리얼 진법 with PythonPS 2023. 4. 3. 16:04
📌 BOJ 5692 팩토리얼 진법 💡 조건 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 최대 5자리인 팩토리얼 진법 숫자가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. 각 테스트 케이스에 대해서, 입력으로 주어진 팩토리얼 진법 숫자를 10진법으로 읽은 값을 출력한다. 수학 유형의 문제 🔖 예제 및 실행결과 예제 1 719 1 15 110 102 0 실행결과 1 53 1 7 8 8 ⌨️ 문제 풀이 입력 받은 숫자를 문자열로 변경한 뒤, 길이(l)를 구한다...
-
[백준] 1676 팩토리얼 0의 개수 with PythonPS 2023. 4. 1. 22:49
📌 BOJ 1676 팩토리얼 0의 개수 💡 조건 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하는 문제. 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 수학 유형의 문제 🔖 예제 및 실행결과 예제 1 10 실행결과 1 2 예제 2 3 실행결과 2 0 ⌨️ 문제 풀이 리스트에 팩토리얼 계산 값을 미리 넣어놓으면 쉽게 해결할 수 있다. N에 해당하는 값을 꺼내 맨 우측부터 좌측 방향으로 이동하며 0이 아닌 수가 나올 때까지 0의 개수가 몇 개인지 세면 된다. 🖥 소스 코드 from sys import stdin arr = [1, 2, 6, 24, 120] n = int(stdin.readline()) if n < 5: print(0) else: for i i..
-
[백준] 14469 소가 길을 건너간 이유 3 with PythonPS 2023. 4. 1. 22:41
📌 BOJ 14469 소가 길을 건너간 이유 3 💡 조건 N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다. 모든 소가 농장에 입장하려면 얼마나 걸리는지 구하는 문제. 첫 줄에 100 이하의 양의 정수 N이 주어진다. 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다. 정렬, 그리디 유형의 문제 🔖 예제 및 실행결과 예제 1 3 2 1 8 3 5 7 실행결과 1 15 ⌨️ 문제 풀이 기..
-
[백준] 1992 쿼드트리 with PythonPS 2023. 3. 31. 17:57
📌 BOJ 1992 쿼드트리 💡 조건 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못한다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 된다. 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하는 문제. 분할정복, 재귀 유형의 문제. 🔖 예제 및 실행결과 예제 1 8 11110000 11110000 00011100 00011100 11110000 111..
-
[백준] 1890 점프 with PythonPS 2022. 8. 9. 17:33
📌 BOJ 1890 점프 💡 조건 N×N 게임판에 수가 적혀져 있다. N (4 ≤ N ≤ 100) 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로..
-
[백준] 1722 순열의 순서 with PythonPS 2022. 8. 9. 17:18
📌 BOJ 1722 순열의 순서 💡 조건 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다. 임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 문제 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나..
-
[백준] 1081 합 with PythonPS 2022. 7. 22. 20:06
📌 BOJ 1081 합 💡 조건 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 문제. 0 ≤ L ≤ U ≤ 2,000,000,000 수학 유형의 문제 🔖 예제 및 실행결과 예제 24660 308357171실행결과 11379854844⌨️ 문제 풀이 가장 먼저 문제를 보며 주목해야할 부분은 L과 U의 범위이다. L과 U의 범위는 최대 20억까지로, 일일히 검사했을 때 최악의 경우에는 0부터 20억까지의 모든 수를 검사해야하기 때문에 문제에서 주어진 2초라는 시간 안에 절대 해결할 수가 없다. (1)번에서 정리한대로, 우리는 L과 U의 범위를 입력받아 일일히 숫자 하나씩 검사하는 방법을 피해 각 숫자의 자릿수를 더해 답을 출력해야 한다. L, U 를 입력받아 L보다 크거나 같고..
-
[백준] 3079 입국심사 with PythonPS 2022. 7. 14. 20:36
📌 BOJ 3079 입국심사 💡 조건 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. (1 ≤ Tk ≤ 109) 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 상근이와 친구들..