본문 바로가기

코딩 테스트/백준93

2230 수 고르기 (자바스크립트) 문제N개의 정수로 이루어진 수열 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이상인 두 수를 고를 수 있다.제한1 ≤ N ≤ 100,0000 ≤ M ≤ 2,000,000.. 2025. 5. 23.
7453 합이 0인 네정수 문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.출력합이 0이 되는 쌍의 개수를 출력한다.====문제 풀이처음에는 a+b+c+d =0 이므로 a+b = -(c+d)를 만족하는 경우를 구하면 되지 않을까 싶었지만 이럴 경우 a+b를 구하는 N^2 이후 이 요소들을 하나씩 끄집어내면서 c+d를 구할려면 N^2*LogN ~ N^3이 되어서 시간 초과가 발생한다. 그래서 a+b.. 2025. 5. 22.
3151 합이 0 (자바스크립트) 문제Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여.. 2025. 5. 22.
1854 K번째 최단경로 찾기(자바스크립트) 문제봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k$k$번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.입력첫째 줄에 n$n$, m$m$, k$k$가 주어진다. (1≤n≤1000$1 ≤ n ≤ 1\,000$, 0≤m≤250000$0 ≤ m ≤ 250\,000$, 1≤k≤100$1 ≤ k ≤ 100$, mk≤3000000$mk ≤ 3\,000\,000$) n$n$과 m$m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 .. 2025. 5. 16.
1800 인터넷 설치 (자바스크립트) 문제오늘 팀전을 다들 열심히 하시는 것을 보고 원장선생님은 세미나 실에 인터넷을 설치해 주기로 마음을 먹으셨다. 하지만 비 협조적인 코레스코 콘도는 원장님께서 학생들에게 인터넷 선을 연결하는 것에 대해서 일부에 대해 돈을 요구하였다.각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P1번은 다행히 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다. 우리의 목표는 N번 컴퓨터가 인터넷에 연결하는 것이다. 나머지 컴퓨터는 연결 되어 있거나 연결 안되어 있어도 무방하다.하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 이.. 2025. 5. 15.
20183 골목 대장 호석 (파이썬) https://www.acmicpc.net/problem/20183문제 풀이 1. 최단거리로 이동하되 그 과정에서 나오는 비용 중 최대 비용이 가장 작은 거리를 찾는 문제.2. 다익스트라로 최단 거리를 찾아가는 과정.3. 이때 힙큐의 우선 순위로 둘 수 있는 것은 (최단 거리 비용과 최대 비용)중 하나인데 노드의 갯수가 10만, 루트의 갯수가 50만이므로 도착 지점에 도달했을 경우 탐색 과정이 끝나는 것이 좋다. 때문에 정답이 되는 최대 비용을 힙큐의 우선순위로 두어서 도착 지점일 경우 반복문이 끝나도록 하면 된다. 4. 힙큐에는 [ 이동하면서 발견한 최댓값, 거리 가중치, 현재 위치 ] 를 삽입5. 방문했던 것들을 기록하기 위해 visited를 선언. visited에는 각 노드별 [ 최단 거리 가중치,.. 2025. 5. 10.
1781 컵라면 (자바스크립트 / 파이썬) 문제상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.문제 번호데드라인컵라면 수123456711332266721451위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작.. 2025. 5. 9.
24042 횡단보도 (자바스크립트) 문제당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 N$N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, 간접적으로 연결되어 있다. 편의상 N$N$ 개의 지역을 1$1$부터 N$N$까지로 번호를 붙이자.당신은 이미 멀리서 교차로의 신호를 분석했기 때문에 횡단보도에 파란불이 들어오는 순서를 알고 있다. 횡단보도의 주기는 총 M$M$ 분이며 1$1$분마다 신호가 바뀐다. 각 주기의 1+i(0≤i$1+i (0 \le i 번째 신호는 i,M+i,2M+i,3M+i,⋯$i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 1$1$분 동안 Ai$A_i$번 지역과 Bi$B_i$번 지역을 잇는 횡단보도에 파란불이 .. 2025. 4. 28.
3687 성냥개비 (자바스크립트) 문제성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)출력각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. =====문제 풀이우선 각 숫자들을 꾸릴 때 필요한 성냥개비들을 구해보면 아래와 같다.const s.. 2025. 4. 26.