Coding Test/BOJ

[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자https://www.acmicpc.net/problem/20551키워드먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.그 다음 M개의 질문을 한다.제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력단, D가 B에 존재하지 않는 경우에는 -1를 출력구현정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다. 템플릿low, high 모두 범위 안에 들어오도록 한다.반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)해당 숫자를 찾은 경우가장 앞에 있는 원..

[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장https://www.acmicpc.net/problem/15810키워드풍선을 담당하는 N명의 스태프대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰각 스태프가 풍선 하나를 만드는 시간(분) A_i를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?구현매개변수 탐색을 이용하여 구현한다.범위가 int 범위를 초과하므로 long 자료형을 이용한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;mid 시간내로 만들 수 있는지 체크한다. mid 시간 내로 만들 수 있다면high = ..

[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기https://www.acmicpc.net/problem/16401키워드반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.구현나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자. 매개변수 탐색을 이용하여 구현한다. 템플릿low, high 값은 항상 범위 내로 설정한다.low = 0high = 길이가 가장 긴 과자 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2..

[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열https://www.acmicpc.net/problem/1351키워드무한 수열 A는 다음과 같다.A_0 = 1A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.0 ≤ N ≤ 10^122 ≤ P, Q ≤ 10^9구현중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.int 대신 long 자료형을 이용하자statch HashMap cacheA_i에서 i일 때 A_i의 값을 저장한다.statc long dp(long index)index가 0인 경우1을 반환한다.캐시값이 존재하는 경우캐시값을 반환한다.A[index] = A_[i..

[BOJ/JAVA] 2302번: 극장 좌석

2302번: 극장 좌석문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.https://www.acmicpc.net/problem/2302키워드공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.“VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.주어진 조건을 만족하면서 사람들..

[BOJ/JAVA] 11052번: 카드 구매하기

11052번: 카드 구매하기요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.https://www.acmicpc.net/problem/11052키워드카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재민규는 돈을 최대한 많이 지불해서 카드 N..

[BOJ/JAVA] 5557번: 1학년

5557번: 1학년상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.https://www.acmicpc.net/problem/5557키워드마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램구현초기값은 항상 맨 앞에 있는 숫자이다.결과..

[BOJ/JAVA] 1612번: 가지고 노는 1

1612번: 가지고 노는 1동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. 이제 원숭이가 1을 가지고 노는 법을 알아보자. 원숭이는 1만으로 이루어진 수를 매우매우매우매우매우매우매우 좋아한다. 그래서 어떤 자연수 N이 있을 때, N의 배수 중에서 1만으로 이루어진 수가 있을 까 생각하게 되었다.https://www.acmicpc.net/problem/1612키워드N의 배수 중에서 1만으로 이루어진 수중에 가장 작은 수의 자릿수구현countNumberLength입력받은 값의 자릿수를 계산하는 메소드입력받은 정수를 String으로 바꾼다.해당 문자열의 길이를 반환한다.s..

[BOJ/JAVA] 1644번: 소수의 연속합

1644번: 소수의 연속합하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.https://www.acmicpc.net/problem/1644키워드하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수구현N이하의 소수 구하기에라토스테네스의 체를 이용하여 소수를 구한다.primeList 소수를 저장한다.N이하 소수의 누적합 구하기..

[BOJ/JAVA] 10830번: 행렬 제곱

10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.https://www.acmicpc.net/problem/10830키워드크기가 N*N인 행렬 A가 주어진다.A의 B제곱을 구하는 프로그램구현matrixMultiply두 정방행렬의 곱을 구하는 메소드시간복잡도 O(N^3)정방행렬의 곱은 다음과 같다.[a1a2a3a4]∗[b1b2b3b4]=[a1b1+a2b3a1b2+a2b4a3b1+a4b3a3b2+a4b4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \\ b_3 &..