[BOJ] 1202 : 보석 도둑(Java)

문제 링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 💡 풀이 문제 풀이의 큰 틀은 우선 입력 받는 보석 [M, V]를 무게(M) 기준으로 오름차순 정렬하여 리스트에 저장합니다. 이때, 무게가 같다면, 가격을 기준으로 내림차순 정렬합니다. 입력 받는 가방 또한, 가방에 담을 수 있는 최대 무게를 기준으로 오름차순 정렬합니다. 그 뒤 탐색을 시작합니다. 탐색은 가방을 기준으로 진행..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 1. 30.
• textsms

[BOJ] 17136 : 색종이 붙이기(Java)

문제 링크 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 💡 풀이 색종이의 크기에 따라 붙여 나아가며 붙일 수 없는 경우 되돌아오는 백트래킹을 이용하여 풀이 할 수 있습니다. 그래프의 (0, 0)부터 차례대로 탐색하며, 0인 경우 옆으로 넘어가고, 1인 경우 붙일 수 있는 여부를 확인해 진행하는 방식을 이용했습니다. BackTracking 백트래킹 함수의 파라미터로는 ( y좌표, x좌표, 지금까지 사용한 색종이 수) 이렇게 3가지를 ..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 1. 23.
• textsms

[BOJ] 17281 : ⚾(Java)

문제 링크 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 💡 풀이 주어진 야구 룰에 따라 구현하면 되는 문제인데, 관건은 자바에서 따로 메서드를 제공하고 있지 않은 순열을 구현하는 부분이었던 것 같습니다. 1번 선수부터 9번 선수의 타격 순서를 비교해가며 최대값을 찾는 것이기 때문에 순열을 이용했습니다. 야구 룰에 맞게 구현만하면 되는 문제입니다. 순열 Permutation이라고 불리는 순열을 사용해 만들 수 있는 모든 타순에 대해 탐색을 진행합니..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 1. 22.
• textsms

[BOJ] 17070 : 파이프 옮기기 1(Java)

문제 링크 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 💡 풀이 파이프를 옮겨가며 끝 점에 도달 할 수 있는 모든 경우의 수를 구하는 문제이기 때문에, DFS를 사용해 풀이했습니다. 또한, 길이가 2인 파이프는 파이프의 끝 점에 따라 시작점이 따라 오는 구조이기 때문에 파이프 끝 점(두 번째 점)만을 이용해 풀이했습니다. 먼저, 움직일 수 있는 경우의 수를 선언해줍니다. 여기서는 가로, 세로, 대각선 방향으로 움직일..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 1. 21.
• textsms

[BOJ] 2143 : 두 배열의 합(Java)

문제 링크 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 💡 풀이 배열 A와 배열 B의 누적합을 저장하는 두 배열 계산해 하나씩 비교하면 시간 초과가 발생합니다. 따라서, 배열 A의 누적합을 저장한 배열을 순회하며, T - a[i]의 값을 B의 누적합 배열에서 찾을 때, 이분 탐색을 이용해 찾습니다. 누적합 배열 각 A, B 배열에 대해 누적합을 저장하는 배열을 ..

• format_list_bulleted 알고리즘/BOJ
• · 2023. 11. 28.
• textsms

[BOJ] 1234 : 크리스마스 트리(Java)

문제 링크 https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 💡 풀이 우선, 전체 색상은 빨간색, 초록색, 파란색으로 3가지 입니다. 따라서, K 레벨에서 장식할 수 있는 경우의 수는 다음과 같이 3가지입니다. 한 가지의 색상만 사용하는 경우 두 가지 색상을 사용하는 경우 세 가지 색상을 사용하는 경우 하지만, 문제 조건에서 각 레벨에 놓으려고 선택한 색의 장난감 수가 같아야 하기 때문에, 두 가지 색상을 사용할 경우는 K가 2의 배수, 세 가지 색..

• format_list_bulleted 알고리즘/BOJ
• · 2023. 11. 27.
• textsms