[백준 - 21758][Gold 5] - 꿀 따기 (JAVA)

문제 링크 https://www.acmicpc.net/problem/2331 문제 입력 첫 번째 줄에 장소의 수 N이 주어진다. 다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다. 출력 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. 구현으로 풀릴까?? 우선 가장 쉬운 방법인 구현을 생각해보자. 벌통의 위치 1개와 꿀벌의 위치 2개를 선정해서 꿀의 합을 구하는 코드를 만들면 조합이기 때문에 다음과 같은 시간복잡도가 나온다. O(N) = (벌통 위치 고르기) + (꿀벌 1 위치 고르기) + (꿀벌 2 위치 고르기) = (N*(N-1)*(N-2))/(3*2*1) ≒ N^3 N의 최대값이 100,000이기 때문에 최대 연산 횟수가 1,000,000,000,000,00..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 28.
• textsms

[백준 - 2331][Silver 4] - 반복수열 (JAVA)

문제 링크 https://www.acmicpc.net/problem/2331 문제 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다. 입력 첫째 줄에 A(..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 17.
• textsms

[백준 - 21610][Gold 5] - 마법사 상어와 비바라기 (JAVA)

문제 링크 https://www.acmicpc.net/problem/21610 문제 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다. N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오. 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 ..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 16.
• textsms

[백준 - 2138][Gold 5] - 전구와 스위치 (JAVA)

문제 링크https://www.acmicpc.net/problem/2138 문제N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오. 입력첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다. 출력첫째 줄에 답을 출력한다. 불가능한 경우에는 -1..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 15.
• textsms

[백준 - 15486][Gold 5] - 퇴사 2 (JAVA)

문제 링크 https://www.acmicpc.net/problem/15486 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 ..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 12.
• textsms

[백준 - 1092][Gold 5] - 배 (JAVA)

문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 ..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 9.
• textsms