[백준 - 12886][Gold 4] - 돌 그룹(JAVA)

문제 링크 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 문제 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다..

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

[백준 - 2342][Gold 3] - Dance Dance Revolution (JAVA)

문제 링크 https://www.acmicpc.net/problem/2342 문제 승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다. DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자. 처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그..

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

[백준 - 15685][Gold 3] - 드래곤 커브 (JAVA)

문제 링크 https://www.acmicpc.net/problem/15685 문제 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다. 2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색..

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

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