문제풀이/백준
-
[백준]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) 이다. - 상근이가 항상 ..
-
[백준]20010: 악덕 영주 혜유 - JAVA문제풀이/백준 2021. 7. 7. 17:08
[백준]20010: 악덕 영주 혜유 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 풀이 🪑 MST를 구하는 활용문제이다. 문제의 조건들을 정리해보자. 마을간 교역로는 양방향이다. 모든 마을은 연결되어있다. 구하는 값은 MST 비용과 MST 내에서 가장 먼 노드간의 거리이다. 🔧 이제 문제 풀이 과정을 생각해 보자. 마을 간 교역로 정보를 입력 받은 후 MST를 구한다. MST를 저장해 둔 다음 MST를 내에서 DFS로 가장 먼 노드간의 거리를 구한다. 가장 먼 노드간의 거리를 구하기 위해선 먼저, 한 정점에..
-
[백준]13392: 구간 나누기2 - JAVA문제풀이/백준 2021. 7. 6. 15:56
[백준]13392: 구간 나누기2 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 풀이 🪑 최댓값의 최솟값! 을 구하는 문제. 이런 문제는 "이분 탐색" 으로 풀 수 있는 문제들이다. (최단거리는 BFS를 떠올리듯..) 먼저 문제의 조건들을 정리해보자. N개의 수를 M개 이하의 구간으로 나눠 구간 점수의 최대 값의 최소값을 구한다. 구간 점수는 구간에 속한 수의 최대값 에서 최소값을 뺀 값이다. N개의 수를 나눌 때는 연속된 순서대로 나눠지면, 각 구간은 한개 이상의 수를 ..
-
[백준]1042: 거짓말 - JAVA문제풀이/백준 2021. 7. 5. 15:23
[백준]1042: 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 🪑 문제를 따라 조건들을 차례차례 정리해 보았다. 지민 -> 진실 OR 과장(되도록 과장 BUT 거짓말 들키기 싫어함) 진실 아는 사람 존재 -> 과장 할 수 없음. 진실을 한 번 이라도 들은 사람은 진실을 아는 사람이다. 🔧 위의 조건들을 토대로 어떻게 풀지 풀이 순서를 적어보았다. 진실을 아는 사람들의 정보를 모은다. 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원..
-
[백준]14890: 경사로 - JAVA문제풀이/백준 2021. 7. 3. 15:00
[백준]14890: 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 🪑 조건에 따라 문제를 잘 읽고 풀어야 하는 구현 문제였다. 확인해 주어야 할 방향은 총 2가지 방향이므로 (열, 행) 열을 확인하는 함수, 행을 확인하는 함수 두개로 나누어 풀어주었다. 🔎 확인할때는 한 방향으로 확인하며 현재 계단의 높이와 다음 계단의 높이차를 확인해 주었다. 계단의 높이차가 1을 초과하면 문제의 조건에 나와있는 "계단의 높이차는 1이어야 한다"를 만족하지 못하므로 바로 false를 반환하도록 하였다. 계단의 높이차가 1이더라도 다음 ..