[백준 - 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

Integer.valueOf VS Integer.parseInt

들어가기전에 int형으로 바꿔주는게 valueOf말고 parseInt가 또 있네?? 알고리즘 문제를 풀다보면 문자열을 숫자로 바꿔야 하는 일이 정말 많다. 특히 입력 값을 받을 때 숫자로 받아야 하는 일이 대부분인데 나는 보통 Integer.valueOf를 위주로 사용했다. 문자열로 바꿀 때 String.valueOf를 사용했는데 Integer도 똑같이 있는 것을 발견하고 그 이후로는 그대로 valueOf를 사용하면서 문제를 풀었다. 하지만 알고리즘 문제를 풀면서 다른사람의 코드를 비교하는데 어떤사람은 Integer.parseInt로 어떤사람은 Integer.valueOf로 사용하고 있다는 것을 발견했다. 문자열을 숫자로 바꾸는 메소드가 2개나 있다는 것이다! 왜 둘다 숫자로 바꿔주는 역할은 같은데 메소..

• format_list_bulleted JAVA
• · 2024. 2. 13.
• 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