문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 이 문제는 distance(행성 사이 거리)가 1인 경우부터 차근차근 구해봐야 일정한 규칙을 발견할 수 있습니다. path: 이동 경로 cnt: 최소한의 공간이동 장치 작동 횟수 same_cnt_times: 같은 cnt가 연속된 횟수 distance path cnt same_cnt_times 행의 갯수 1 1 1 1 2 2 11 2 1 3 1..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 풀이 구현 문제입니다. 주사위를 굴렸을 때 회전축이 지나는 2개의 면을 제외한 4개의 면이 어떻게 변하는지 이해한다면 풀 수 있는 문제입니다. 면 \ 회전 방향 동 서 북 남 1(윗면) 1 -> 4 1 -> 3 1 -> 5 1 -> 2 2(북쪽 면) 그대로 그대로 2 -> 1 2 -> 6 3(동쪽 면) 3 -> 1 3 -> 6..

문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 DP를 이용해서 한번 구했던 답을 다시 연산하지 않도록 합니다. 문제에서 주어진 아래의 조건에 의해 3차원 배열 dp의 크기는 (21) * (21) * (21)입니다. if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20) w 함수를 선언하고 재귀 연산 중간에 한번 구했던 답은 다시 연산하지 않도록 아래의 코드를 추가합니..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 DP를 이용합니다. 문제의 예제를 dp table에 나타내면 아래와 같습니다. 물품 \ 가치 합 1 2 3 4 5 6 7 (6, 13) 0 0 0 0 0 13 13 (4, 8) 0 0 0 8 8 13 13 (3, 6) 0 0 6 8 8 13 14 (5, 12) 0 0 6 8 12 13 14 입력받은 물품들을 (weight..

문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 원의 둘레 = \( diameter \times \pi \) 이므로, 첫 링의 한바퀴 이동 거리를 구할 수 있습니다. 위의 원리로 첫링이 한바퀴 도는 동안 i번째 링의 이동거리를 구할 수 있습니다. 기약 분수를 구하기 위해선 분모, 분자에 GCD(최대공약수)를 곱해줍니다. 코드 import sys def euclidean(a, b): if b == 0: return a return euclidean(b, a % b) n..

문제 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 next_permutation 알고리즘의 부등호만 바꾸면 이전 순열을 구현할 수 있습니다. 코드 import sys def prev_permutation(lst): l = len(lst) x = -1 for i in range(l - 2, -1, -1): if lst[i] > lst[i + 1]: x = i break if x == -1: return [-1] for j in range(l - 1, x, -1): if lst[x] > lst[..