백준, boj) 1509. 팰린드롬 분할 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 2. 문제 개요 어떤 문자열을 팰린드롬으로 분할하려고 한다. 분할의 개수의 최솟값을 구하시오, 즉 원소의 개수가 최소가 되도록 해야 함. 3. 문제 힌트 처음에 분할의 최솟값이라고 하길래 분할하면 분할했지 분할의 최솟값은 뭐지?라고 생각했다. 질문란 이런 곳을 찾아보니 분할의 경우의 수가 아니고 분할했을 때 원..
boj, 백준) 1947. 선물 전달 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 문제 설명 대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오. 모든 사람은 선물은 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다. 3. 문제 힌트 기존의 그룹(n - 1명)에 최적화된 답을 알고 있다고 가정하자. n - 1명이 있는데, 새로운 사람x가 들어온다. ( 이제 n명이 됨. dp[n]을 구할 것. ) (1) x가 1번사람이 받은 선물과 바꾼다. (1번 사람의 선물이 아닌, 1번 사람이 받은 선물이다.) (2) x가..
백준, boj) 4781. 사탕 가게(C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 문제 상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 �� www.acmicpc.net 2. 문제 설명 사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하자. 3. 문제 힌트 돈의 양이 소수점인데, 100을 곱해서 자연수로 만들어주자. 그럼 배낭문제랑 똑같다. dp[n]는 n원을 썼을 때 얻을 수 있는 최대 값으로 정의하자. 그러면 만약에 dp[n]에서 100원짜리를 고른다고 할 때, dp[n]..
백준, boj) 4991. 로봇 청소기
1. 문제 링크 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청 www.acmicpc.net 2. 문제 개요 로봇 청소기를 사용해 청소를 하려고 한다. 경로는 유저가 직접 정할 수 있다. 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하자. 3. 문제 힌트 더러운 지역의 개수가 최대 10개밖에 되지 않기 때문에 순열(permutation)을 사용해서 구현 가능하다. DP로 푸는 것은 아마 외판원 순회 ..
boj, 백준) 1043. 거짓말 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 2. 문제 개요 지민이는 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기를 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수밖에 없다. 당연히, ..