목록Data Structure & Algorithms/Algorithms-Problems (11)
yeonuel-tech

https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 1. 문제 설명 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다 같은 조에 속한 원생들은 서로 인접해 있어야 한다 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. 2..

https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 1. 문제 설명 이때, 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라 위 예시의 정답은 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번이다. 2. 접근법 처음에는 가장 많이 색을 칠해야 하는 것을 한번에 칠하고 그 이후에 각 문제를 하나씩 색칠해 가는 방식으로 풀었음 하지만, 문제 요구 사항 중 하나는 ..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 1. 문제 설명 n 가지 종류 동전이 있고 각 동전들은 가치가 주어진다 이 동전들을 사용해서 k원을 만들때 사용한 동전의 최소 개수를 출력해라 2. 접근법 내 포스팅 글 중에 "동전1" 문제 풀이가 있다 그 문제와 상당히 유사하다 그래서, dp 알고리즘을 사용해서 풀 수 있다 즉, 분할 할 수 있는 하위 문제들 중에서 최소값 + 1이 현재 만드려는 가치의 값이된다 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 설명 n가지 종류의 동전이 있다. 각 동전이 나타내는 가치는 다르며 각각의 동전은 몇 개라도 사용할 수 있다 이때, k원(가치)가 되도록 만들 수 있는 경우의 수를 구해라 사용한 동전의 순서만 다른 것은 같은 경우이다 2. 접근법 이 문제는 dp 알고리즘으로 풀었다 dp 알고리즘으로 문제를 풀려면 확인해야 하는 중요한 것들이 있다 그 중에 하나는 상위 문제를 하위 문제들로 분할 가능하며 ..

https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 1. 문제 설명 n이 주어졌을 때, 길이가 n인 올바른 괄호 문자열의 개수를 구해야함 2. 접근법 이 문제는 창의적 사고력과 집중력이 요구되는 좋은 문제인것 같다 일단, 우리가 구하고자 하는 올바른 괄호 문자열의 두 가지 특징을 살펴보자 1. 시작하는 문자는 항상 여는 괄호 '('이다 2. 문자열의 길이는 짝수이다 시작하는 문자가 닫힌 괄호 ')' 인 경우를 생각해보면 그 뒤에 어떤 문자열이 와..

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 1. 문제 설명 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다. 각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다 남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구해라 2. 접근법 첫번째로 생각한 풀이법은 브루트 포스 방식이다 다음 순열을 이용해서 뮤탈리스크가 n개..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 1. 문제 설명 곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어짐 또한, 볼륨의 리스트인 V가 주어짐 V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다 하지만, 0보다 작..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 문제 설명 크기가 N×N인 도시가 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이..