PS5 [백준] 2631번 - 줄세우기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 줄세우기 -> https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이미 정렬되어 있는 아이들 제외하고 정렬되지 않는 아이들을 옮긴다. 이때 옮겨지는 아이의 최소 수를 구해야 되므로 정렬되어 있는 아이들의 최대 수(Lis)를 구하여 전체 아이들의 수(n)에서 빼준다. C++ 소스코드) 2021. 9. 3. [백준] 5557번 - 1학년 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 1학년 -> https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net F (Idx, PartialSum) : 0번째 수부터 Idx까지의 합의 개수 DP에 적용할 점화식을 다음과 같다고 하자. 그럼 점화식을 F(Idx + 1, PartialSum + number[Idx + 1]) + F(Idx + 1, PartialSum - number[Idx + 1])로 통해 올바른 등식의 .. 2021. 7. 27. [백준] 2186번 - 문자판 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판 -> https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net F(x, y, index): 점 (x, y)에서 index이후의 부분 문자열을 만들 수 있는 경로의 개수 점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다. C++ 소스코드) 2021. 7. 27. [백준] 1448번 - 삼각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 그리디 (Greedy) - 삼각형 만들기 -> https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 세 변으로 만들 수 있는 삼각형 중 세 변의 합의 최대를 구하는 문제. N이 100만이므로 O(nC3)으로 완전 탐색이 불가능한다. 최대만 구하면 되므로 모든 변을 내림차순으로 정렬한 뒤, 삼각형을 이룰 수 있는 변 3개가 존재하면 답을 출력한다. C++ 소스코드) 2021. 7. 27. [백준] 1188번 - 음식 평론가 (C++) 문제 및 풀이 문제) 백준 - 수학 - 음식 평론가 -> https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 예제와 n과 m의 경우의 수를 관찰하며 해결했다. 소시지를 하나로 이어 붙인다. n개의 소시지를 무조건 m명의 평론가한테 주려면 소시지를 최대 m-1번 잘라 m개의 배수개로 토막 낸다. n과 m이 서로소일 때는 m - 1번 자르는 것이 답임을 알 수 있고, 서로소가 아닐 경우에는 m - 1번에서 n-1번 잘린 위치와 m - 1번 잘린 위치의 공통 위치만큼 제외해준다. 이 수는 최대공약수임을 알 수 있다. C++ 소스코드) 2021. 7. 27. 이전 1 다음 반응형
