Coding Test/Problem Number (75) 썸네일형 리스트형 [Java] 키 순서 [2458번] https://www.acmicpc.net/problem/2458예제 입력16 61 53 45 44 24 65 2예제 출력11예제 입력26 71 31 53 45 44 24 65 2예제 출력22예제 입력36 31 22 34 5예제 출력30문제 접근입력학생의 수 N, 두 학생을 비교한 횟수 MM개의 줄에 작은 학생(a) 큰 학생(b)출력자신의 키가 몇 번째인지 알 수 있는 학생의 수 출력문제 해결시작이 주어지지 않았으므로 플로이드 워셜 문제배열의 자기자신은 0, 나머지는 무한대로 초기화플로이드 워셜의 점화식을 사용a학생이 b학생보다 작거나 b학생이 a학생이 작다면 키를 비교할 수 있다는 의미배열[a][b] check == N(학생 수)와 같다면 모든 학생과 직,간접적으로 연결이 되어있다는 의미로 자신의 키가.. [Java] 회장뽑기 [2660번] https://www.acmicpc.net/problem/2660예제 입력151 22 33 44 52 45 3-1 -1예제 출력12 32 3 4문제 접근입력회원 수 (Node)친구 사이(Vertex)-1 -1 입력 시 종료출력회장 후보 점수와 후보 수 출력회장 후보 오름 차순 출력직접적인 친구 관계 ⇒ 1점친구의 친구 관계 ⇒ 2점친구의 친구의 친구 관계 ⇒ 3점친구 관계 중 관계의 점수가 낮을수록 가까운 사이의 친구가 많다는 의미 ⇒ 회장 후보 → 건너 건너 친구인 게 길면 길 수록 회장 후보가 아니라는 것문제 해결1번 친구 ~ 2번, 3번, 4번, … , N번 친구까지 관계 점수…N번 친구 ~ 1번, 2번, 3번, …, N-1번 친구까지 관계 점수플로이드 워셜로 관계 점수(코스트)를 구해야 함제일 낮.. [Java] 미로 만들기 [2665번] https://www.acmicpc.net/problem/2665예제 입력181110011011010010100110101110110001000111001100011101100011000111예제 출력12문제 접근입력방의 수 n이 주어짐 (1 ~ 50)n의 줄만큼 1과 0으로 이루어진 길이 n 입력 → 0 : 검은방 / 1 : 흰방출력흰 방으로 바꾸어야 할 최소 검은 방의 개수문제 해결시작 : 0, 0 ~ 목표 : n-1, n-1dx, dy 배열로 이동할 좌표 저장 필요dist 배열에 0, 0을 제외한 나머지 무한대로 초기화현재 좌표(x, y)에 dx, dy를 더했을 때 배열의 범위가 벗어나면 무시map[다음X][다음Y]가 검은방(0)이라면 1, 흰 방(1)이라면 0을 change 변수에 저장dist[다.. [Java] 택배 배송 [5972번] https://www.acmicpc.net/problem/5972예제 입력16 84 5 32 4 04 1 42 1 15 6 13 6 23 2 63 4 4예제 출력15문제 접근입력헛간 N(노드), 소들의 길 M(간선)M개의 줄만큼 A_i(start), B_i(end), C_i(소의 수, weight)출력찬홍이가 있는 위치 N을 목표로 하고, 1 ~ N까지 갈 때 필요한 최소 여물 개수 → 1 ~ N까지의 최소 가중치 출력문제 해결간선은 양방향 그래프소의 수 C_i는 0 ~ 1,000까지로 음수 가중치가 없기 때문에 다익스트라로 풀이dist[N+1] 배열을 사용, 출발지인 1번 헛간은 0, 나머지 헛간은 무한대로 초기화dist[연결노드] > dist[현재노드] + 연결노드까지의 가중치 → 갱신 및 Queue.. [Java] 게임을 만든 동준이 [2847번] https://www.acmicpc.net/problem/2847예제 입력13555예제 출력13예제 입력245375예제 출력26문제 접근입력레벨의 수 N (1 ~ 100)클리어 시 점수 (1 ~ 19,999)항상 답이 존재하는 경우만 주어짐출력점수를 몇 번 감소 시키면 되는 지 출력문제 해결점수 1 감소 시 1씩 카운트가장 마지막을 시작으로 마지막 - 1이 마지막보다 작아지게, 마지막 -2가 마지막 - 1 보다 작아는 것을 반복기존 풀이 [메모리 : 14208 KB / 시간 : 108 ms]public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader.. [Java] 카드 문자열 [13417번] https://www.acmicpc.net/problem/13417예제 입력133M K U5A S D F G7B A C A B A C예제 출력1KMUASDFGAAABCBC문제 접근입력테스트 케이스 개수카드 개수카드 개수만큼 문자 입력 (모두 대문자)출력사전 순으로 가장 빠른 문자열 출력문제 해결가장 처음의 카드를 가지고 온 뒤 이후 카드는 왼쪽 또는 오른쪽으로 배치 가능Deque를 이용해서 맨 앞 카드를 기준으로 왼쪽 오른쪽에 붙이면 됨기존 풀이 [메모리 : 30480 KB / 시간 : 284 ms]public static void main(String[] args) throws Exception { StringBuilder sb = new StringBuilder(); BufferedRead.. [Java] 거스름돈 [14916번] https://www.acmicpc.net/problem/14916예제 입력113예제 출력15예제 입력214예제 출력24문제 접근입력거스름돈 액수 n출력거스름돈 동전의 최소 개수거슬러 줄 수 없으면 -1문제 해결짝수와 홀수이기 때문에 거스름돈이 5보다 작고 홀수 일 때는 거슬러 줄 수 없음% 5의 나머지가 짝수일 때는 5원으로 거슬러 줄 수 있는 최대로 거슬러주고% 5의 나머지가 홀수일 때는 5원으로 거슬러 줄 수 있는 최대에서 5원을 1번 덜 거슬러 줌 → 무조건 짝수가 나옴기존 풀이 [메모리 : 14196 KB / 시간 : 104 ms]static final int TWO = 2;static final int FIVE = 5;public static void main(String[] args) thr.. [Java] 상자넣기 [1965번] https://www.acmicpc.net/problem/1965예제 입력181 6 2 5 7 3 5 6예제 출력15예제 입력2101 2 3 4 5 6 7 8 9 10예제 출력210문제 접근입력상자의 개수상자의 개수만큼 상자의 크기출력한 상자에 넣을 수 있는 최대 상자 개수문제 해결1개의 상자에는 반드시 1개가 포함(자기 자신) ⇒ dp 배열을 1로 초기화현재 상자 사이즈가 dp[j] 상자 사이즈보다 크다면 dp[i] = max(dp[i], dp[j] + 1)dp[j]에 몇 개의 상자가 들어있을진 모르겠지만 어찌됐든 dp[j]에는 그보다 작은 상자들이 누적되어있었을 것이기 때문기존 풀이 [메모리 : 15408 KB / 시간 : 156 ms]public static void main(String[] arg.. 이전 1 2 3 4 ··· 10 다음
