문제https://www.acmicpc.net/problem/32200문제 설명 $N$개의 샌드위치가 존재한다.최소 $X$cm이상, 최대 $Y$cm이하의 길이로 샌드위치를 잘라서 먹을 것이다.샌드위치를 잘랐을 때 $X$cm 미만이 남았다면 버린다.샌드위치로 해결할 수 있는 끼니 개수의 최댓값과 버려지는 샌드위치 조각의 합의 최솟값을 구해라. 풀이현재 샌드위치의 길이가 $X$cm 보다 작다면 나머지에 더한다.샌드위치를 먹을 수 있는 최솟값인 X로 나누었을 때 몫과 나머지를 구한다.2에서 구한 나머지를 최솟값으로 나눈 샌드위치에 더해가며 최소의 나머지를 구한다. 예시문제에 나와있는 1번 예제로 예시를 들어보자.1. $[11,10,17,5,23,28]$ 총 6개의 샌드위치가 존재한다.2. 최소 10cm ~..

문제https://www.acmicpc.net/problem/12934문제 설명각 턴으로 이루어진 게임이 존재한다.턴은 1턴부터 시작해서 n턴까지 이루어져 있다.i턴의 승자에게 i점의 점수가 부여된다.윤호와 동혁이의 점수 x와 y가 주어진다.게임을 진행했을 때 윤호가 x점, 동혁이가y점이 될 수 있는지 판별한다.게임이 가능하다면 윤호가 최소 몇 번 이겨야 하는지도 구한다. 풀이x와 y의 최대 값은 $10^{12}$이다.나올 수 있는 최댓 값 $x=$ $10^{12}$ , $y=$ $10^{12}$ 일 때를 기준으로 현재 점수가 진행 가능한 게임인지 판별한다.불가능하다면 -1을 출력한다.게임 진행이 가능하다면 진행 가능한 최대 턴 수를 구한다.게임을 이겨야 하는 최소 횟수를 구한다.(n턴)최소 횟수가 되기..

문제https://www.acmicpc.net/problem/10844문제 설명  45656과 같이 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.N이 주어질 때 길이가 N인 계단 수가 총 몇 개 있는지 구한다.0으로 시작하는 수는 계단 수가 아니다. 풀이만약 계단 수가 21이라면 21을 통해 만들 수 있는 세자리 계단수는 210, 212이다.이처럼 계단 수의 맨 뒷자리를 기준으로 +1, -1을 하면 다음 수의 계단수를 구할 수 있다.이러한 조건을 가지고 N = 1, N = 2일 때를 구해보자.N = 1일 경우01234567890111111111 만들 수 있는 계단수는 1,2,3,4,5,6,7,8,9이다.따라서 i로 끝나는 계단수의 수를 표로 표현해 보면 위 표처럼 나오는 것을 볼 수 있다.N ..

문제https://www.acmicpc.net/problem/10425문제 설명n번째 피보나치 수 $F_n$이 주어진다.$F_n$이 몇 번째 피보나치 수인지 구한다.이 때 가능한 경우가 여러 개라면 가장 큰 인덱스를 출력한다. 풀이$F_n$의 최댓값이 $10^{21000}$ 이므로 10**21000까지의 피보나치 수를 구한다.이분탐색을 통해 mid 인덱스의 피보나치 수와 $F_n$을 비교한다.fibo[mid]가 $F_n$보다 작다면 s = mid 크거나 같다면 e = mid로 바꾸어 범위를 줄인다.마지막으로 나온 값(인덱스)을 출력한다.코드import sysinput = sys.stdin.readlinefibo = [0,1,1,2,3]MAX = (10**21000)num = 0while num 시간복잡도..

문제https://www.acmicpc.net/problem/15810문제 설명N명의 스태프와 M개의 풍선이 존재한다.N명의 각 스태프가 풍선 하나를 만드는 데 걸리는 시간 $A_i$가 주어진다.M개의 풍선이 다 만들어지는 최소 시간을 출력한다. 풀이$N$명의 스태프가 M개의 풍선을 모두 만드는데 걸리는 시간을 완전탐색을 통해 검사해보자.최악의 경우 $10^6$명의 스태프가 존재하고 각 스태프가 풍선을 만드는 데  $10^6$ 분이 걸린다.그렇다면 $1$부터  $10^6$초까지 모두 탐색하며 모든 풍선이 만들어 질 수 있는지 확인해야 할 것이다.따라서 최대 시간을 T라고 했을 때 시간복잡도는 $O(N*T) = O(10^6 * 10*6) = O(10^12)$이다.문제에서 요구하는 시간인 1초를 초과하게 되..

문제https://www.acmicpc.net/problem/15965문제 설명 2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다.K번째 소수를 구한다. 풀이문제에서 구하는 K의 최댓 값은 500,000이며 이를 구하면 7,368,787이다.그럼 500,000번째소수를 찾기 위해서는 약 1~7,000,000까지의 수를 모두 탐색해야 한다.def is_prime(N): flag = True for i in range(2, N): if N % i == 0: flag = False break기본적인 소수 찾기 알고리즘의 시간복잡도는 $O(N)$이다.2부터 N까지의 수를 모두 탐색하며 소수를 판별한다...

문제https://www.acmicpc.net/problem/19699문제 설명  농장에 N마리의 소가 있다.소들의 몸무게의 합이 소수(Prime)이 되도록 M마리의 소를 선별해야 한다.조건에 맞게 소를 선별했을 때 나올 수 있는 몸무게의 합을 모두 출력하시오 풀이에라토스테네스의 채를 이용하여 모든 소의 몸무게의 합까지 존재하는 소수를 모두 구한다.그 후 조합을 이용하여 나올 수 있는 몸무게의 경우의 수를 모두 구하여, 그 중 소수만을 찾는다.에라토스테네스의 채를 통해 최댓값까지 모든 소수를 찾는다.combination 함수를 통해 모든 조합을 검사한다.prime[weight] == true해당 몸무게의 합이 소수이므로 res 배열에 넣는다.res 배열을 오름차순으로 정렬한 후 출력한다.코드import ..

문제https://www.acmicpc.net/problem/6593문제 설명  각 변의 길이가 1인 정육면체로 이루어져있는 상범 빌딩을 탈출해야 한다.각 칸에서 인접한 6칸(동, 서, 남, 북, 상, 하)으로 1분의 시간을 들여 이동할 수 있다.시작 지점(S)으로부터 출구(E)를 통해 탈출해야 한다.탈출할 수 있다면 " Escaped in x minute(s)."를 출력한다.탈출할 수 없다면 "Trapped!"를 출력한다. 문제에서 각 위치에서 다음 위치로 이동할 때 가중치가 1로 동일하다고 명시되어 있기에BFS를 통해 3차원 배열을 탐색했다.풀이입력받은 3차원 배열을 탐색하여 시작 지점(S)과 도착 지점(E)을 찾는다. 시작지점부터 BFS탐색을 진행한다.상, 하, 좌, 우, 위, 아래를 dx, dy,..

문제https://www.acmicpc.net/problem/18126문제 설명너구리 구구는 총 N개의 방을 가지고 있다.입구를 포함한 모든 방은 1부터 N까지 번호를 가지고 있다.이 때 입구는 1번이다.구구는 입구에서 가장 먼 방에 아이스크림을 숨기려고 한다.구구가 집 입구에서 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구해라.  BFS 혹은 DFS를 통해 가장 먼 방까지의 거리를 구하는 문제다.이 때 문제에서 "모든 길은 서로 오고 갈 수 있다."라는 말이 있기 때문에 양방향 그래프로 구현했다.풀이입력받은 간선 정보를 통해 양방향 그래프를 생성한다.1번 노드가 입구 즉 루트 노드이므로 1번 노드부터 탐색을 진행한다.순차적으로 방을 이동하면서 최대 거리를 갱신한다.코드import sysfrom ..

문제https://www.acmicpc.net/problem/11725문제 설명루트 없는 트리가 주어진다.트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구해라.단순 DFS를 사용하여 각 노드의 부모를 구하는 문제이다.풀이루트 노드가 1번이므로 1번 노드부터 DFS탐색을 시작한다. 현재 방문한 노드를 이전 노드의 값(부모 노드)으로 방문 처리한다.2번 노드부터 순차적으로 부모를 출력한다.코드import syssys.setrecursionlimit(10**5)input = sys.stdin.readlinen = int(input())graph = [[] for _ in range(n+1)]visited = [0 for _ in range(n+1)]for i in range(n-1): v1,v2 ..