코딩브론즈

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 풀이 1) 그래프에 지름길 정보를 담고 distance 배열 초기화 ( distance[i] = i ) 2) 0부터 다익스트라 시작 3) 1씩 증가시키면서 distance 배열에 최소 이동거리를 갱신 주의사항 1) 방문체크는 필요없다. package com.baekJoon; import java.io.BufferedReader; import java.io.IOException; impo..

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 1) 범위내의 자연수 크기(1000)의 boolean 형 배열 isPrime을 선언한다. 2) 0과 1은 소수가 아니므로 2부터 1000까지 isPrime을 true로 설정한다. 3) 2부터 에라토스테네스의 체를 적용하여 isPrime을 false로 걸러준다. 4) 주어진 N개의 수를 뽑아 배열의 인덱스에 대입했을 때 true 면 answer++ 5) answer 출력 주의 사항 1) 이 문제는 시간초과날 일도 없지만 범위가 넓은 다른 문제였다면 완전탐색 시 시간초과가 날 ..

programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 풀이 1) 맵생성 2) participant를 맵에 담을거임 2-1) participant[i] 가 없을경우 : 1 2-2) participant[i] 가 있을경우 : 기존값에 +1 3) completion와 비교해서 있으면 1씩 감소 4) 마지막에 value가 1인 애가 딱 하나 나올거임. Map.Entry를 이용해서 key를 출력 주의사항 1) x im..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 1) 방문체크할 visited[] 배열을 만듬. 사이즈는 200001. N이 최대 10만이고 * 2 하면 20만이 나올 수 있으므로. 2) bfs를 돈다 class의 멤버는 cnt 2-1) X = 2 * X : cnt = cnt 2-2) X = X - 1 : cnt = cnt + 1 2-3) X = X + 1 : cnt = cnt + 1 3) X = K 가 되면 끝 4) ..

www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 풀이 1) K가 0이 될때까지 반복문을 돌린다. 2-1) N/2 >= M 이면 N과 K를 -- 2-2) N/2 = M 이면 M을 출력 3-2) N/2 < M 이면 N/2를 출력 주의사항 1) x package com.baekJoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.Strin..

www.acmicpc.net/problem/12018 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 풀이 1) PriorityQueue queue에 각 과목을 수강하기위한 최소 마일리지를 담을거임. 2) PriorityQueue pq (내림차순)에 신청인원들이 넣은 마일리지를 담는다 3) 경우를 나누어 따져본다. 3-1) 신청인원 >= 수강인원 : pq에서 수강인원수 만큼 뽑고 가장 마지막에 뽑은 마일리지 +1을 queue에 담는다. 3-2) 신청인원 < 수강인원 : queue에 1을 담는다. (마일..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 1) path[N+1] 배열을 생성한다. 배열의 값은 1에서 해당 number에 도달하기위해 필요한 연산의 최소 횟수이다. 2) path 배열의 값을 1000000으로 초기화 시켜준다. (문제에서 10^6 까지라고 했으므로) 3) path[1] = 0 으로 초기화 한다. (1에서 1로 가는 연산의 횟수는 0이므로) 4) n = 2부터 N까지 for문을 돌면서 3가지 경우를 따진다 n % 3 = 0 인 경우 : path[n] = Math.min(path[n/3] + 1, path[n]) n % 2 = 0 인 경우 : pa..

www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 1) 2차원 배열에 주사위 정보 저장 dice[N][6]; 2) 경우의 수는 총 6가지이다. 첫번째 주사위의 각 면을 바닥으로 했을 경우를 다 따져보자. 3) A-F, B-D, C-E 끼리 마주보는것을 잘 인지해야한다. 4) 예제의 경우 첫 번째 주사위의 A가 밑면일 경우 F가 윗면. B, C, D, E 중에 최댓값을 구하여 더해준다. 4-1) 첫 번째 주사위의 윗면은 F 이므로 두 번째 주사위의 밑면은 D, ..