Algorithm/Baekjoon Online Judge

    [Java] 백준 2873 (롤러코스터) Platinum 3
    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 모두 짝수라면, 표 중 단 한 곳을 제외하고 모든 곳을 방문할 수 있다. 시작점이 흰색인 체스판으..

    [Java] 백준 12904 (A와 B) Gold 5
    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'라면 삭제한 뒤, 뒤..

    [Java] 백준 12970 (AB) Gold 4
    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) * ..

    [Java] 백준 1744 (수 묶기) Gold 4
    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 두 개는 더하는 것이 값이 크다. ..

    [Java] 백준 1285 (동전 뒤집기) Gold 1
    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번째 행..

    [Java] 백준 2109 (순회강연) Gold 4
    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 배열의 총..

    [Java] 백준 16933 (벽 부수고 이동하기 3) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16933 (벽 부수고 이동하기 3) Gold 1

    Problem : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Approach BFS문제이다. 백준 14442 (벽 부수고 이동하기 2) 문제에 조건이 하나 더 달린 문제이다. 여기서의 visited배열은 4차원 배열이다. visited[n][m][k][a] 는 (n, m) 위치를 k번 벽을 부신 채로 낮(a = 0) 혹은 밤(a = 1)에 방문했다는 뜻이다. 문제 풀이의 주요 로직은 다음과 같다. 낮이라..

    [Java] 백준 14442 (벽 부수고 이동하기 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14442 (벽 부수고 이동하기 2) Gold 3

    Problem : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Approach 대표적인 BFS문제이다. 일단 visited[i][j][k] 는 (i, j) 위치에 k번 벽을 부순 채로 도달했는지를 나타내는 배열이다. 문제를 푸는 주요 BFS 로직은 다음과 같다. 현재 위치에서 상하좌우 방향으로 벽이 아니라면 cnt++ 한 후, 이동한다. (이 때 visited 배열에 벽을 부순 횟수는 증가시키지 않고 표시..

    [Java] 백준 16954 (움직이는 미로 탈출) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16954 (움직이는 미로 탈출) Gold 4

    Problem : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 변하는 방법은 위에서 아래로 한 칸씩 내려오는 방식이다. 문제를 푸는 로직은 다음과 같다. 현재 위치가 벽이 아니라면, 현재 위치 포함, 상하좌우 대각선4방향으로 이동한다. 벽을 위에서 아래 방향으로 한 칸씩 내린다. 무한 루프를 방지하기 위해 방문 여부를 나타내는 flag 변수를 하나 둔다...

    [Java] 백준 3055 (탈출) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3055 (탈출) Gold 5

    Problem : https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 문제를 푸는 주요 로직은 다음과 같다. 다음에 물이 찰 예정인 곳은 비버가 방문할 수 없으니 물을 먼저 전파시키고 비버를 이동시킨다. 물을 전파시킨다. 비버를 이동할 수 있는(물이 차지 않은) 곳들을 방문한다. 즉, 비버따로 물따로 각각 BFS가 수행되어야 한다. (ps. cnt 배열을 사용하지 않고 Point 클래..

티스토리툴바