문제 https://www.acmicpc.net/problem/11047준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.문제첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)문제첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. Algorithm동전의 가치를 스택 구조를 이용해 큰 값 부터 이용한다큰 값 부터 몫과 나머지를 이용해 최대한..
분류 전체보기
문제https://www.acmicpc.net/problem/2230N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.입력첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.출력첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있..
문제 https://www.acmicpc.net/problem/1476준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16..
문제 https://www.acmicpc.net/problem/7662이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하..
문제알고리즘다익스트라를 활용하여 Y노드를 포함해서 Z까지의 최단경로와, Y노드를 지나지 않고 Z까지의 최단경로를 구하는 문제이다.Y노드를 무조건 지나는 경로는 X to Y + Y to Z의 최단경로를 서로 더해주면 된다.Y노드를 지나지 않는 최단경로를 구할때는, 다익스트라를 반복하면서 Y노드를 방문할때 해당 계산을 무시하고 건너뛰도록 설정해주면 된다.코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)n, m = map(int, input().split())graph = [[] for _ in range(n + 1)]for _ in range(m): u, v, w = map(int, input().split()) graph[u].a..
문제 풀이N은 500000 이하이고, 제한 시간은 1.5초이므로 O(n^2) 풀이로는 해당 문항을 해결하지 못한다.출력 양식에서 하나씩 값을 출력할 때, 앞에 있는 것 전부를 조사하지 않고 일부만 조사해서 답을 얻을 수 있는 알고리즘을 구상해야함에 주의하며 생각해보자.오른쪽 탑 A가 왼쪽 탑 B보다 높이가 높다면, A보다 오른쪽 탑들에 대해서는 B의 정보가 필요가 없어진다. 왜냐하면 B까지 가기 전에 A에 막힐 것이기 때문이다.따라서 스택을 활용하여 현재 탑을 쌓을 것인데, 현재보다 높이가 작은 탑을 pop하여 없애버리고, 현재 높이 이상인 처음 만난 탑부터를 남겨두는 과정을 반복하면, 탐색에 걸리는 시간이 O(1)이 되므로, 종합적으로 O(N) 시간에 해결이 가능하다.코드#include using n..
16953번: A → Bimport sys sys.setrecursionlimit(10000) a,b=map(int,input().split()) ans=0 def pan(ans,a,b): while 1: if b %2 ==0: b//=2 ans+=1 else: b=str(b) if b[-1] == '1': b=int(b[:-1]) ans+=1 else: return -1 if b return -1 elif ..
문제 https://www.acmicpc.net/problem/2178N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수..
문제알고리즘전형적인 bfs문제이다. 시작점인 a부터 b까지의 최소거리를 구하면 된다.각 지점까지의 거리를 -1, 초기값으로 설정하고 a를 시작점으로 하여 bfs를 수행해주면 된다.bfs를 수행하면서 graph 조건을 보고 거리가 갱신이 안되어있다면 현재 지점까지의 거리+1로 해당 거리를 수정해주면 된다.코드import sysinput = sys.stdin.readlinefrom collections import dequea,b = map(int,input().split())n,m = map(int,input().split())graph = [[] for _ in range(n + 1)]for _ in range(m): x, y = map(int, input().split()) graph[x]...
https://www.acmicpc.net/problem/11866문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)출력예제와 같이 요세푸스 순열을 출력한다.코드#inc..
https://www.acmicpc.net/problem/10972 문제1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1입력첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.출력첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.코드#include #include using names..
문제알고리즘문제에 "이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다." 라는 조건이 존재하므로, 어떤 길에서 이동할 수 있는 길이 1이하 칸이 존재한다면 해당 마을에는 막다른 길이 존재하게 된다.그러므로 모든칸을 조사하면서 상,하,좌,우로 움직일 수 있는 칸의 개수를 카운팅하면서 1이하인 칸이 존재한다면 해당 마을은 막다른 길이 된다.코드import sysinput = sys.stdin.readliner, c = map(int, input().split())arr = [input().strip() for _ in range(r)]dx = [-1, 1, 0, 0]dy = [0, 0, 1, -1..
