[Java] 백준 12931 (두 배 더하기) Gold 4

Problem : https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net Approach Greedy 한 방법으로 숫자의 2진수 비트를 활용하여 문제를 풀이하였다. 먼저 문제 풀이에 사용한 자바 메소드를 살펴보자. Integer.toBinaryString(int n): 숫자 n을 받아서 문자열 이진수로 바꾼 뒤 리턴한다. Integer.bintCount(int n): 숫자 n의 이진수에서 1의 개수를 리턴한다. 숫자를 만드는 데에 +1..

→2021.06.19

Algorithm/Baekjoon Online Judge

[Java] 백준 1201 (NMK) Platinum 3

Problem : https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net Approach 알고 보면 쉬운데 그걸 알기까지가 어려웠던 Greedy 문제이다. 먼저 유효하지 않은 n, m, k를 찾아보자. (m + k) - 1 > n: 1 ~ n 까지의 숫자가 모두 증가하는 수열 혹은 감소하는 수열에 속한다고 가정할 때, 두 수열을 더했을 때의 길이 m + k = n + 1이다. (두 수열은 적어도 하나의 숫자를 공유하기 때문이다.) 그렇기 때문에 (m + k) - 1 > n 라면 길이 m의 증가수열 + 길이 k의 감소수열은 만들 수 없다. 각 수열을 구하는 방법은 다음과 같다. 길이 m의 증가수열을 만..

→2021.06.01

Algorithm/Baekjoon Online Judge

[Java] 백준 2873 (롤러코스터) Platinum 3

Problem : https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net Approach Greedy 문제지만 구현이 좀 필요하다. 일단 그리디한 생각은 다음과 같다. r행 c열 표가 존재할 때, r, c 중 하나라도 홀수라면 표의 모든 곳을 방문할 수 있다. ㄹ 모양 혹은 ㄹ 을 y=x 대칭시킨 모양으로 방문한다면 모든 곳을 지날 수 있다. r, c 모두 짝수라면, 표 중 단 한 곳을 제외하고 모든 곳을 방문할 수 있다. 시작점이 흰색인 체스판으..

→2021.05.25

Algorithm/Baekjoon Online Judge

[Java] 백준 12904 (A와 B) Gold 5

Problem : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net Approach Greedy한 문제이다. 주어진 문자열 S -> T를 만드는 것이 아니라, 규칙을 역으로 적용하여 T를 S길이와 같은 문자열로 만들고, 그 문자열과 S를 비교하여 같은지를 체크하면 된다. 주요 로직은 다음과 같다. 문자열 T의 맨 오른쪽 글자가 'A'라면 그냥 삭제한다. 문자열 T의 맨 오른쪽 글자가 'B'라면 삭제한 뒤, 뒤..

→2021.05.23

Algorithm/Baekjoon Online Judge

[Java] 백준 12970 (AB) Gold 4

Problem : https://www.acmicpc.net/problem/12970 Approach Greedy 문제이다. 먼저 간단한 규칙을 알아보자. A의 개수 a, B의 개수 b일 때, (A, B) 쌍의 최대 개수는 a * b 개이다. (A~AB~B 형태의 문자열) 그리고 길이가 N 인 문자열에서 (A, B) 쌍의 최대 개수는 A의 개수가 N / 2개이고, B의 개수가 N - a 개일 때이다. 또한, a개의 A와 b개의 B로 만들 수 있는 쌍의 범위는 0 ~ a * b개이다. 문제 풀이의 주요 로직은 다음과 같다. A와 B를 각각 늘리고 줄이면서 a * b >= k 인 (a, b) 를 찾는다. 길이 N 만큼 B를 가득 채우고, 앞에서부터 a - 1 개만큼 A를 삽입한다. (현재 (a - 1) * ..

→2021.05.23

Algorithm/Baekjoon Online Judge

[Java] 백준 1744 (수 묶기) Gold 4

Problem : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net Approach Greedy한 문제이다. 아무 위치에 있는 두 수를 선택해도 되기 때문에, 먼저 정렬을 수행하는게 선택하기에 편하다. 문제 풀이에 앞서, 상식을 이용할 필요가 있다. 음수 두개를 곱하는 것이, 음수 두개를 더하는 것보다 값이 크다. 음수와 0은 곱하는 것이, 양수와 0은 더하는 것이 값이 크다. -1 두 개는 곱하는 것이, 1 두 개는 더하는 것이 값이 크다. ..

→2021.05.21

Algorithm/Baekjoon Online Judge

[Java] 백준 1285 (동전 뒤집기) Gold 1

Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Approach Greedy + Bitmask 문제이다. 주요 로직은 다음과 같다. N x N 행렬이고, sum은 뒷면 동전의 총 개수이다. 행을 기준으로 뒤집을 행을 선택한다. (이 부분은 2^n 개수 만큼 존재한다.) 101 이라면 0, 2번째 행을 뒤집는다. 이제 선택한 행들을 뒤집을 건데, 열을 기준으로 먼저 뒤집는다. 101 이라면, 0,1,2 열 순서대로 0번째 행..

→2021.05.21

Algorithm/Baekjoon Online Judge

[Java] 백준 2109 (순회강연) Gold 4

Problem : https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net Approach 우선순위 큐를 사용한 그리디(Greedy) 알고리즘 문제이다. 먼저 pay 기준 내림차순으로 정렬된 우선순위 큐가 필요하다. pay가 같을 경우에는 day가 더 작은 것이 우선이다. 그리고 주어진 입력 d의 최대 크기만큼의 cost 배열을 선언한다. cost[i] 는 i일에 얼마짜리 강의를 하는지를 저장한다. cost 배열의 총..

→2021.05.19

Algorithm/Baekjoon Online Judge

[Java] 백준 1202 (보석 도둑) Gold 2

Problem : 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 Approach 우선순위 큐를 활용한 Greedy 문제이다. 접근법을 떠올렸다면 쉽게 구현할 수 있다. (PriorityQueue 이용하여) 먼저 보석과 가방을 각각 무게 기준 오름차순으로 정렬한다. 각 가방에 대하여 가방의 무게보다 작은 보석들을 pq에 넣는다. (pq는 보석의 가치 기준 내림차순의 우선순위를 가진다...

→2021.04.17

Algorithm/Baekjoon Online Judge

[Java] 백준 12100 (2048 Easy) Gold 2

Problem : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net Approach BruteForce + 단순 구현 문제이다. break 문을 적절하게 넣어서 시간을 절약할 수 도 있겠지만, 그냥 4x4x4x4x4 = 1024 가짓수의 경우를 모두 검사하였다. 배열을 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 미는 작업을 하는 메소드를 정의한 뒤, 4방향 중 중복허용하여 5가지 방향을 뽑아 적용하면 된다. 최대 크기 블..

→2021.04.05

티스토리툴바