링크 https://www.acmicpc.net/problem/2217 난이도(solved.ac 참고) 실버3 풀이 문제 풀이 방법은, 그냥 내림차순으로 나열한 다음에 a_list[인덱스] * (인덱스+1)의 최댓값을 구하면 끝난다. a_list[인덱스]는, 예제의 경우 내림차순하면 15 10 이 되는데, 각 로프에 모두 고르게 중량이 걸리게 되므로 15를 선택한다면 15만큼만 들 수 있고, 10을 선택한다면 (10 * 2) = 20만큼 들 수 있다. 이 생각을 토대로, a_list[인덱스]의 값은 작아지고 인덱스는 커지는 상황에서 결국 들 수 있는 값인 a_list[인덱스] * (인덱스 + 1)의 최댓값을 구한 것이다. (여기서 인덱스+1을 해 준 이유는, 인덱스는 0부터 시작하기 때문이다.) 사실 어..

링크 https://www.acmicpc.net/problem/9237 난이도(solved.ac 참고) 실버5 풀이 좀 허무했다. 처음에 내가 너무 어렵게 생각했는데, 이게 실버5가 맞나..? 라는 생각이 들어서 일단 접어뒀다가 다시 풀고 금방 맞았다. 이 문제에서의 핵심은, 총 걸리는 시간은 배열 내 최대값 + 그 인덱스의 값이기 때문에, 큰 값을 가장 앞에 둬야 된다는 것이다. 큰 값이 뒤에 있다면, 이미 인덱스가 많이 증가한 상태이기 때문에 결국 최종 걸리는 시간은 더 길어지게 된다. t 배열에 각자 다 자라는데 며칠이 걸리는지에 대한 값을 넣었고, 그 값을 내림차순으로 정렬했다. 그렇게 되면, 다 자라는 데 오래 걸리는 묘목을 앞 순서에 배치시켜서 묘목이 자라는 데 걸리는 시간 외에, 그 묘목을 ..

문제 기술 0부터 n-1까지 번호가 붙여진 n명의 사람들의 친구관계가 주어져 있다. 다음은 6명의 사람들에 대한 친구관계를 보여준다. 친구관계로 연결되어 있는 집단의 개수와 가장 큰 집단의 크기 (사람 수), 가장 작은 집단의 크기를 구하는 프로그램을 작성하시오. 위의 그림에서 집단은 2개이고 가장 큰 집단은 {1, 2, 3, 5, 6}으로서 크기는 5이고 가장 작은 집단은 {0, 4}로서 크기는 2이이다. 요구조건: 친구관계를 인접리스트로 표현하고, 탐색방법은 깊이우선탐색을 이용한다. 첫 번째 줄에 사람들의 수 n(1이상 1,000이하 정수)와 친구 관계 수 m(0 이상 300,000 이하 정수)가 주어진다. 다음 m개의 각 줄에 친구 관계를 나타내는 두 사람의 번호가 주어진다. 입력 7 6 1 2 1..

문제 기술 m×n 크기(m은 행의 개수, n은 열의 개수)의 배열로 표현되는 미로가 있다. 1은 갈 수 있는 곳을 나타내고, 0은 갈 수 없는 곳을 나타낸다. 미로의 가장 위에서 가장 아래로 내려가는 최단 경로의 길이 (지나는 1의 개수)를 구하는 프로그램을 작성하시오. 미로의 각 위치에서 상하좌우로 인접한 곳으로만 갈 수 있다. 가는 길이 없으면 -1을 출력한다. 입력 6 10 // m n은 각각 2이상 100이하 정수 0110000011 1101111101 1101010111 1111010111 0100111000 1011110111 출력 12 나의 코드 0부터 3까지 i에 대한 for문을 돌리면서 동서남북으로 좌표 이동을 했고, 미로 밖으로 안나갔을 경우, 그리고 아직 방문하지 않았을 경우 해당하는..

문제 기술 2) 다음과 같은 형태의 일방통행 도로망에서 호텔에서 공항까지 가는 버스를 운행하고 있다. 호텔에서 공항까지 가는 도로망의 구조는 다음과 같다. 위쪽 도로에 n개 교차로 u1, u2, …, un이 있고, 아래쪽 도로에 n개 교차로 l1, l2, …, ln이 있다. u0(=l0)는 호텔을 나타내고, un+1(=ln+1)은 공항을 나타낸다. 그리고 i

문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 4 6 5 3 5 7 5 1 1 3 2 5 4 8 가장 아래 행의 셀로부터 오른쪽 위쪽 대각선 방향 혹은 위쪽 방향 혹은 왼쪽 위쪽 대각선 방향으로만 가면서 가장 위의 행의 셀까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 ..

문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 9 6 5 3 6 7 5 2 1 3 2 5 4 8 (1, 1) 셀 (1, 1)에서 오른쪽 방향 혹은 위쪽 방향으로만 가면서 셀 (m, n)까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고, 이 배..

문제 기술 프로그래머스 lv3 입국심사 문제를 변형한 문제이다. 공항에서 사람들의 입국을 심사하는 심사대가 k개있다. 사람들이 입국심사를 받기 위하여, 심사대 바로 앞에서 한 줄로 서서 기다린다. k개의 심사대 중 하나가 비어있으면(심사받는 사람이 없으면), 먼저 도착한 사람이 비어 있는 이 심사대에서 심사를 받는다. 입국심사를 받기 위한 각 사람의 심사대 앞에 도착하는 시간과 심사받는데 걸리는 시간이 주어진다. 각 사람이 심사대 앞에 도착한 시간에 대한 정보는, 바로 이전 사람이 심사대 앞에 도착한 시간과의 차이(분)로 주어진다. 각 사람이 심사를 받기 위하여 기다리는 시간 (심사시간은 제외)의 평균을 소수점 이하 1자리까지 (소수점 이하 2째 자리에서 반올림) 출력하는 프로그램을 작성하시오. 예를 들..

문제 기술 n(1이상 10,000이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 s1 혹은 s2, ..., 혹은 sk개의 계단만 오를 수 있으며, 각 계단은 밟을 때 비용이 있다. 여기서 1 ≤ s1 < s2 < ... < sk이다. 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합이 최소가 되도록 하면서 올라가고자 한다. 이때의 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 양의 정수 n과 k가 주어진다. 다음 줄에 s1, s2, ..., sk를 나타내는 k개의 양의 정수가 주어진다. 세 번째 줄에 가장 아래 계단부터 위로 차례대로 n개의 각 계단을 밟을 때 비용이 양의 정수로 주어진다. 출력 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의..

문제 기술 n(1이상 10,000이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 1개, 3개 혹은 4개의 계단만 오를 수 있으며, 각 계단은 밟을 때 비용이 있다. 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합이 최소가 되도록 하면서 올라가고자 한다. 이때의 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 양의 정수 n이 주어진다. 다음 줄에 가장 아래 계단부터 위로 차례대로 n개 각 계단을 밟을 때 비용이 양의 정수로 주어진다. 출력 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합의 최소값을 출력한다. 입력 예 6 2 7 2 9 12 3 출력 예 5 나의 코드 import sys def stair(n, price): if 1