알고리즘/백준
-
[백준] 13397번 : 구간 나누기2 -자바(JAVA)알고리즘/백준 2022. 7. 3. 00:01
https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 문제 해석 N개의 수로 이루어진 1차원 배열이 있다. 배열을 M개 이하의 구간으로 나누어 구간의 점수를 최댓값을 최소로 하려고 합니다. 1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다. 2. 배열의 각 수는 모두 하나의 구간에 포함되어야 한다. 이때 구간의 점수는 구간에 속한 수의 최댓값과 최솟값의 차이입니다. 예를 들어 배열이 1 5 4 6 2 ..
-
[백준] 2110번 : 공유기 설치 - 자바(JAVA)알고리즘/백준 2022. 7. 2. 00:01
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 해석 집 N개가 수직선 위에 존재하고 집 여러 개가 같은 좌표를 가지는 일은 없다. 공유기 C개를 설치하려고 하는데 한 집에는 공유기를 하나만 설치할 수 있다. 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. 집의 개수와 공유기의 개수가 주어질 때 두 공유기 사이의 최대 거리를 출력하라. 문제 풀이 전 설계 집의 개..
-
[백준] 16566번 : 카드 게임 - 자바(JAVA)알고리즘/백준 2022. 6. 28. 00:01
https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해석 철수와 민수는 카드 게임을 즐겨한다. 1. N개의 빨간색 카드가 있으며 1부터 N까지 번호가 매겨져 있다. 2. N개의 파란색 카드가 있으며 1부터 N까지 번호가 매겨져 있다. 3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다. 4. 철수와 민수는 고른 카드 중 1장을 뒤집어진 상태로 낸다. 5. 카드 번호가 큰 사람이 ..
-
[백준] 1799번 : 비숍 - 자바(JAVA)알고리즘/백준 2022. 6. 27. 00:01
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해석 서양 장기인 체스에 대각선 방향으로 움직일 수 있는 비숍이 있습니다. 비숍의 위치라 B라고 했을 때 다음 그림처럼 움직일 수 있습니다. 이때 색칠된 부분에는 비숍을 놓을 수 없지만 지나갈 수는 있다고 하겠습니다. 이와 같은 체스판에 서로가 서로가 잡을 수 없는 비숍을 놓는다면 최대 7개의 비숍을 넣을 수 있습니다. 비숍의 최대 개수를 구하는 프로그램을 작성하세요. 체스판의 크기는 10 이하의 자..
-
[백준] 17136번 : 색종이 붙이기 - 자바(JAVA)알고리즘/백준 2022. 6. 26. 00:01
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 해석 다섯 종류의 색종이가 존재하고 각 종류의 색종이는 5개씩 가지고 있다 (총 25개) 크기가 10 x 10인 종이 위에 붙이려고 한다 각각의 칸은 0 또는 1이 적혀 있고 1이 적힌 칸은 모두 색종이로 덮여야 한다. 0이 적힌 칸에는 색종이가 있으면 안된다. 색종이는 종이의 경계 밖으로 나가서는 안된다. 종이가 주어졌을 때 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수..
-
[백준] 2243번 : 사탕상자 - 자바(JAVA)알고리즘/백준 2022. 6. 22. 00:01
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 문제 해석 사탕의 맛이 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕이며 1,000,000은 가장 맛없는 사탕입니다. 사탕상자의 손을 댄 횟수는 10만번 A,B 또는 A,B,C가 입력으로 주어진다. A = 1 이라면 사탕을 꺼내는 경우이다. A = 2 라면 사탕을 넣는 경우이다. 이때 B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그..
-
[백준] 1725번 : 히스토그램 - 자바(JAVA)알고리즘/백준 2022. 6. 21. 00:01
https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 해석 다음과 같은 히스토그램이 주어졌을때 내부의 넓이가 가장 큰 직사각형을 그리려고 합니다. 이때 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하세요 문제 풀이 전 설계 문제에서 직사각형의 넓이가 20억을 넘지 않는다고 하였으므로 int형을 사용해도 될 것 같습니다. 히스토그램의 가로 칸의 최대수는 10만이기 때문에 O(NlogN) 시간복잡도로 해결해야 할 것..
-
[백준] 12100번 : 2048(Easy) - 자바(Java)알고리즘/백준 2022. 6. 18. 00:01
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 해석 2048게임을 예전에 해본적이 있어서 이해가 어렵지 않았습니다. 만약 간단하게 한번 이 게임을 해본다면 더 이해하기 쉬울 것 같습니다. https://play2048.co/ 2048 Join the numbers and get to the 2048 tile! Careful: this game is extremely addictive! play2048.co 문..