문제풀이
-
[백준]20005: 보스몬스터 전리품 - JAVA문제풀이/백준 2021. 7. 20. 15:59
[백준]20005: 보스몬스터 전리품 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 풀이 🪑 입력받는 정보가 많아서 복잡해 보이지만 알고보면 구현 + BFS문제였다. 문제의 조건을 정리해 보자. 전리품은 한 번이라도 피해를 준 플레이어에게 지급된다. 최대 몇명의 플레이어가 전리품을 가져갈 수 있는지 알아낸다. 각각의 플레이어는 보스에게 최단거리로 이동하여 보스 칸에 도달하자마자 공격을 시작한다. 플레이어의 공격은 동시에 이뤄지며 같은 위치에 여러 플레이어가 위치..
-
[백준]14728: 벼락치기 - JAVA문제풀이/백준 2021. 7. 19. 16:04
[백준]14728: 벼락치기 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 풀이 🪑 이러한 문제 유형은 배낭문제(knapsack)이라는 대표적인 DP유형이다. 배낭문제를 예에에전에 풀어본적은 있어서 이 문제가 DP라는건 언뜻 기억이 났지만 접근 방법이 기억 나지 않아 헤멨던 문제이다. DP라는 느낌이 들면 일단 그림을 그려보면서 이해해 보는 것이 가장 좋은 것 같다! 문제의 조건을 살펴보자. 배낭문제와 매핑해서 생각해 보자. 시험의 단원이 의미하는 바는 배낭문제의 ..
-
[백준]2632: 피자판매 - JAVA문제풀이/백준 2021. 7. 17. 16:51
[백준]2632: 피자판매 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 풀이 🪑 손님이 원하는 크기의 피자만큼 판매할 수 있는 경우의 수를 계산하는 문제로 다양한 풀이 방법이 존재하는 문제이다. 먼저 문제의 조건 부터 정리해 보자. A, B의 피자는 다양한 크기의 여러 조각으로 나누어져 있다. 한 종류의 피자를 2조각 이상 판매시 연속된 조각으로 잘라 판매하며 피자 조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자 조각는 A조각으로만 이루어 질 수 있고, B조각으로만 이루어 질..
-
[백준]2539: 모자이크 - JAVA문제풀이/백준 2021. 7. 16. 14:57
[백준]2539: 모자이크 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 풀이 🪑 조건을 만족하는 가장 작은 수를 구하는 문제!! 바로 이분탐색 문제이다. 문제의 조건을 보자. 모든 색종이의 크기는 모두 같고 정사각형이다. 색종이 크기는 한 변의 길이이다. 원하는 크기의 모든 색종이가 존재한다. 모든 색종이는 밑변에 맞추어 붙인다. 또한 겹쳐 붙일 수 있다. 주어진 색종이이 장수로 이러한 조건에 맞춰 잘못 칠해진 칸을 가릴 수 있는 가장 작은 색종이의 크기를 구한다. 🔧 풀이 과정을 정리해 보자! 색종이의 크기를 기..
-
[백준]2550: 전구 - JAVA문제풀이/백준 2021. 7. 15. 15:59
[백준]2550: 전구 2550번: 전구 첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에 www.acmicpc.net 풀이 🪑 LIS에 대한 개념이 없었더라면 LIS에 대해 이해부터 해야 하므로 어려웠을 문제이다. LIS를 알았다면 어렵지 않게 풀 수 있었을 문제였다. 🙋♀️ 우선 나는 LIS문제를 풀어본 적이 있었지만 오래전이라 기억이 나지 않았다. 그래서 LIS부터 다시 공부하였다! 🔹 LIS(Lowes Increasing Subsequence) - 최장 증가 수열이라는 뜻이다. - 예를 들면 [5, 6, 1, 2, 3] 이라는 배열이 있을때..
-
[백준]20444: 색종이와 가위 - JAVA문제풀이/백준 2021. 7. 14. 15:07
[백준]20444: 색종이와 가위 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 풀이 🪑 색종이 컷트컷트 하는 문제로 이분탐색을 사용하는 문제였다! 사실 처음부터 이분탐색으로 풀어야겠다 하는 문제는 아니었다. 처음에는 n번으로 자를 수 있는 색종이의 개수를 백트랙킹으로 풀려고 생각했다가 N, K의 범위와 시간제한 0.1초인걸 보고 이분탐색이구나,, 했다. 이제 문제의 조건을 정리해보자. 색종이는 직사각형이며 색종이를 자를 때는 한 변에 평행하도록 자른다. 한 번에 한 경로의 모든 색종이를 다 자른다. 이미 자른 곳은 또 자를 수 없다. 🔧 문제 풀이 순서를 생각해 보자. N에 따른 K를 구할때, 가로로 ..
-
[백준]5710: 전기 요금 - JAVA문제풀이/백준 2021. 7. 13. 21:56
[백준]5710: 전기 요금 5710번: 전기 요금 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지 www.acmicpc.net 풀이 🪑 간단한듯 조금 복잡한 수학적 사고력과 연산을 요구했던 문제였다. 문제를 정리해보자! 사용량에 따라 전기요금을 부과한다. 상근이와 이웃의 요금 합, 요금 차를 알려주며 이때 상근이가 내야 할 금액을 구해야 한다. 상근이는 항상 이웃보다 적은 요금을 낸다. 정답을 유일하다. 🔧 이제, 문제 풀이 순서 및 아이디어를 떠올려보자. 상근이가 내야 하는 금액의 범위는 0 ~ (A의 요금 / 2) 이다. - 상근이가 항상 ..
-
[프로그래머스]거리두기 확인하기 - JAVA문제풀이/프로그래머스 2021. 7. 11. 16:26
[프로그래머스]거리두기 확인하기 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 🪑 카카오 인턴십 코딩테스트 2번 문제이다. 문제를 정리해 보자. 대기실은 5X5로 5개가 있다. 응시자 끼리 맨해튼 거리 2 이하로 앉지 말아야 한다. ..