본문 바로가기

dp 문제

알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 경찰차 (2618) Java 링크 : https://www.acmicpc.net/problem/2618 문제 설명 : 더보기 어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 29. [BOJ 백준] 카드 게임 (11062) Java 링크 : https://www.acmicpc.net/problem/11062 문제 설명 : 더보기 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다. 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오. 예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 29. [BOJ 백준] 제단 (5626) Java 링크 : https://www.acmicpc.net/problem/5626 문제 설명 : 더보기 상근이는 성적 향상을 기원하며 N열짜리 제단을 만들기로 했다. 제단의 각 열의 높이는 모두 정수이며, 가장 처음에 모든 열의 높이는 0이다. 제단은 다음과 같은 과정을 통해서 만들어진다. 먼저, 같은 높이를 가지는 연속하는 열을 선택한다. 그 다음, 선택한 첫 열과 마지막 열을 제외한 모든 열의 높이를 1만큼 올린다. 아래 그림은 제단을 쌓는 과정의 예시이다. 수백년이 흐르는 동안 많은 도둑들이 제단의 일부 열을 훔쳐갔다. 상근이의 손자의 손녀의 손자의.... 손녀는 남은 제단의 높이를 가지고, 가능한 제단의 경우의 수를 세려고 한다. 제단의 높이가 주어졌을 때, 남아있는 제단의 높이와 일치하는 제단의 개수를..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 28. [BOJ 백준] 가장 큰 정사각형 (1915) Java 링크 : https://www.acmicpc.net/problem/1915 문제 설명 : 더보기 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 : 더보기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 : 더보기 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 예제 입력 : 더보기 4 4 0100 0111 1110 0010 예제 출력 : 더보기 4 접근법 : 1) 어떻게 풀 것인가? N이 1,000이고, N^2으로 모든 경우의 수를 체..

티스토리툴바