[Java] 백준 21775 (가희와 자원 놀이) Gold 5

Problem : https://www.acmicpc.net/problem/21775 21775번: 가희와 자원 놀이 T턴에 걸쳐서, 각 턴에 수행된 연산 카드의 id를 한 줄에 하나씩 출력해 주세요. www.acmicpc.net Approach 간단한 구현 문제이다. (본인은 간단하지 않았다.) 먼저 사용할 자료구조들을 생각해 보았다. 구현 문제에선 어떤 자료구조를 사용할 것인가가 중요한 포인트같다. 턴을 수행하는 사람의 번호 -> sequence 배열 주어진 연산카드 -> 배열 or 큐 개인공간 -> 사람마다 공간 할당(메모리 초과) -> Map 사용 (key, value) == (자원카드 번호, 소지한 사람 번호) 공용공간 -> 불필요 (Map에 없으면 다 공용공간에 있는 것) 번호가 n인 사람이 ..

→2021.06.02

Algorithm/Baekjoon Online Judge

[Java] 백준 21774 (가희와 로그 파일) Gold 3

Problem : https://www.acmicpc.net/problem/21774 21774번: 가희와 로그 파일 2000년부터 2020년까지 연도 중에, 윤년인 것은 2000, 2004, 2008, 2012, 2016, 2020년 입니다. www.acmicpc.net Approach 문자열을 파싱하여 DP를 구성하고, 이분 탐색의 lowerbound, upperbound를 활용해야 하는 문제이다. 문제 풀이의 로직은 다음과 같다. 먼저 문자열을 파싱한다. 주어진 시각 문자열이 YYYY-MM-DD hh:mm:ss 형식이고 순서대로 주어지므로, -:와 공백문자를 없애면 자연스럽게 정렬이 된 상태가 된다. (본인은 Long 타입으로 형변환을 하였지만, String 타입이어도 자연스럽게 사전순으로 정렬 상..

→2021.06.02

Algorithm/Baekjoon Online Judge

[Java] 백준 21773 (가희와 프로세스 1) Gold 5

Problem : https://www.acmicpc.net/problem/21773 21773번: 가희와 프로세스 1 1초일 때 부터 4초일 때 상황을 그림으로 나타내면 아래와 같습니다. 아래 그림에서 주황색은 특정 시점에 스케쥴러가 선택한 프로세스를 의미합니다. www.acmicpc.net Approach 우선순위 큐(PriorityQueue) 를 이용한 문제이다. 문제의 로직은 다음과 같다. 레디 큐에서 가장 우선순위가 높은 프로세스를 꺼내 1초동안 실행시킨다. 꺼낸 프로세스를 제외한 레디 큐에 있는 모든 프로세스의 우선순위는 1증가한다. 위 로직을 구현하려면, 먼저 우선순위 큐의 정렬 기준을 확립해야 한다. 프로세스의 우선순위 기준 내림차순이 필요할 것이다. 이제 우선순위큐에서 프로세스를 하나 뽑..

→2021.06.02

Algorithm/Baekjoon Online Judge

[Java] 백준 1891 (사분면) Gold 4

Problem : https://www.acmicpc.net/problem/1891 1891번: 사분면 첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1≤d≤50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y|≤2 www.acmicpc.net Approach 분할 정복(Divide & Conquer)을 구현한 문제이다. 아래와 같이 두 가지 기능을 구현하여야 한다. 그리고 순서대로 수행하면서 답을 도출한다. 주어진 사분면 숫자의 위치 (x, y)를 찾는다. 그리고 그 위치에 주어진 이동 횟수를 더한 위치를 찾는다. 구한 위치의 사분면 숫자를 구한다. 1번 기능의 경우, 주어진 사분면 숫자를 앞에서부터 한..

→2021.06.01

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

티스토리툴바