목록문제풀이 (42)
이호진
문제 설명 n,m이 주어졌을 때 n개의 동전 종류가 주어지고 그 동전으로 m원을 만드는데 필요한 동전의 최소개수를 출력한다. 풀이 dp리스트를 전부 큰값으로 초기화하고 dp[0]=0으로 설정한다. dp[0]은 코드에서 x원짜리 동전이 있을 때 x원을 만들기위해 필요한 동전의개수는 1개이므로 그때 사용하게 된다. 예를 들어 7원짜리 동전이 있을 때, 7원을 만들 수 있는 방법은 7원짜리 동전 하나를 사용하는것이 최소이다. 점화식을 세우면 d[j]=min(d[j],d[j-i]+1)
문제 설명 예를 들어 높이가 19,14,10,17인 떡이 나란히 있고 절단기 높이를 15로하면 자른뒤 떡의 높이는 15,14,10,15가 되고 잘린 떡의 길이의 총합은 6이다. 손님의 요청이 왔을 때, 요청한 총길이가 m일 때, 적어도 m만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 최댓값을 구하시오 풀이 이진탐색으로 남은 떡 길이에서 정한 값을 뺀 값의 총합을 m과 비교하여 최댓값을 구할 수 있다. 맨 처음에 start=1, end=max(arr)로 잡고 mid를 그 중간값으로 설정한다. arr의 경우마다 for문으로 현재 길이가 mid보다 크다면 그 차이값을 total에 저장하고 m과 비교한다. 그 값이 m보다 작으면 더 많이 잘라야하므로 end를 mid-1로 설정한다. 그 값이 m과 같거나 크다면..
풀이 정렬 후 가장 큰 값과 두 번째로 큰 값을 저장하고 k번 반복할 동안 가장 큰 값을 더해주고 한번 두 번째로 큰 값을 더한다. m=0이될 때까지 반복한다. n,m,k=map(int,input().split()) arr=list(map(int,input().split())) arr.sort() fir=arr[-1] sec=arr[-2] result=0 while True: for i in range(k): if m==0: break result+=fir m-=1 if m==0: break result+=sec m-=1 print(result)
문제 설명 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝..
문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다..
문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도..
문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,..
문제 설명 내 생각 입력을 가지고 다익스트라 알고리즘을 적용하면 출발노드인 1부터 거리가 출력된다. 그 거리 중 가장 큰 값과 가장 큰 값의 노드번호, 가장 큰 값과 같은 값이 몇개 있는지 출력한다. 예를 들어 이 문제에서 주어진 입력으로 다익스트라 알고리즘에 출발노드1로 적용하면 [INF, 0, 1, 1, 2, 2, 2] 가 출력되는데 2가 가장 큰 값이고 첫 번째로 2가 나오는 노드는 4번노드, 그리고 2가 세번 나온다. 그래서 출력은 4 2 3 import heapq INF=int(1e9) n,m=map(int,input().split()) start=1 graph=[[]for i in range(n+1)] for i in range(m): a,b=map(int,input().split()) gra..
문제 설명 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다. 1번 학생의 성적
문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 ..