문제 준규가 가지고 있는 동전은 총 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의 배수) 첫번째 케이스 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 두번째 케이스 10 4790 1 5 10 50 100 500 1000 5000 10000 50000 출력 첫째 줄에 K원을 만드는데 필요..

문제 알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이 때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. ㅇ를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다. 입력 K1KA5CB7 출력 ABCKK13 내가 제출한 풀이 - 정답 import sys import re # 숫자 제거한 오름차순 문자 리스트 s = sys.stdin.readline().strip() word_list = sorted((re.sub("\d", "", s))) # 문자 제거한 숫자 num = re.sub("[a-zA-Z]", "", s) sum_res = 0 for n in num: sum_res += int(n) pri..

문제 행복 왕구의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서 있습니다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있습니다. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 c2에 있을 떄 이동할 수 있는 경우의 수는 6가지입니다. a1에 있을 떄 이동할 수 있는 경우의 수는 2가지입니다. 입력 a1 출력 2 내가 제출한 풀이 - 구현실패 (방향 벡터 선언된 걸 보고 풀음) 방향 벡터를 사용하는 것은 알고 있었으나, 2차원 배열에서 한 리스트당 동 서 남 북으로 ..

문제 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다. 00시 02분 55초 01시 27분 45초 입력 5 출력 11475 내가 제출한 풀이 - 정답 import sys n = int(sys.stdin.readline().strip()) result = 0 for i in range(0, n + 1): # 1시간이 3600초 if i % 10 == 3: result += 3600 cont..

문제 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위쪽으로 한 칸 이동 D : 아래쪽으로 한 칸 이동 최종적으로 도착할 좌표(X, Y)를 공백 기준으로 출력합..

문제 한 마을에 모험가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대터할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁급합니다. N명의 모험가에 대한 정보가 주어졌을 떄, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요. 단, 모든 모험가가 그룹에 참여하지 않아도 됩니다. 입력 5 2 3 1 2 2 첫째 줄에는 모험가 N명을 입력합니다. 둘째 줄에는 모험가 N명의 공포도를 입력합..

문제 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 떄, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰수는 ((((0 + 2) x 9) x 8) x4) = 567입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다. 입력 02984 출력 576 정답 import sys s = sys.stdin.readline().strip() result = int(s[..

그리디 알고리즘이란? 그리디 알고리즘 또는 탐욕벅이라고 불린다. 현재 상황에서 가장 좋은 정답을 찾는 알고리즘이지만, 항상 최적의 해를 보장할 수 없다. 코딩 테스트에서는 대부분 그리디 알고리즘을 통해 얻은 해가 최적의 해가 되는 상황을 부여하기 때문에 가장 최적의 해를 찾아 문제를 풀 수 있어야 한다. 여러가지 예시를 보고 이해를 해보자. 문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. 1-1. N에서 1을 뺍니다. 1-2. N을 K로 나눕니다. 입력 25 4 출력 5 정답 import sys n, k = list(map(int, sys.stdin.readline().stri..