코딩하기 좋은날

https://www.acmicpc.net/problem/2281 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 주어진 사람의 이름의 길이와 공책의 한줄 길이가 주어질 때 사람의 이름을 공책에 적습니다. 사람 사이에는 빈칸이 한칸 있어야하고 이런식으로 끝까지 적을 때 공책의 오른쪽끝 여백의 길이들의 제곱의 합의 최솟값을 구하는 문제입니다. 따라서 모든 경우를 다 해봐야 하므로 dp를 이용하여야 합니다. dp식을 어떻게 세울지 고민해보면 각 사람의 이름이 공책의 어디 위치에 들어가야 하는지가 필요합니다. 이때 행 / 열 /사람 의 정보까지 모두 넣기에는 메모리가 부족한데 잘 생각해보면 공책의 몇행에 쓰는지에 대한 정보는 필요가 없습니다. 따라서 dp를 2차원으로 선언 합니다. dp[i][j..

https://www.acmicpc.net/problem/7579 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 여러개의 앱이 실행 중일때 각 앱을 비활성화 하는 비용과 그로인해 얻을 수 있는 메모리가 있을 때 요구하는 메모리를 확보할 수 있는 최소의 비용을 구하는 문제입니다. 모든 경우를 다 해봐야 하므로 dp를 이용하여야 합니다. dp식을 어떻게 만들지 생각해 보면 2차원 dp를 선언하고 dp[i][j] 의 의미는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미합니다. 따라서 아래식과 같이 dp[i][j]에서 i번째 앱을 비활성화 시킨 경우와 그렇지 않은 경우중 max값을 취하면서 반복문을 돌아주어야 합니다. if(j-cost[i] >= 0) dp[i][j] = ma..

https://www.acmicpc.net/problem/11570 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 주어진 음들이 주어질 때 상덕이와 희원이가 노래를 부릅니다. 이때 이 두사람은 전에 음을 변경할 때 힘이 들게 되는데 이 수치가 abs(현재음-전에불렀던음) 입니다. 이 수치가 최소화 될 수 있는 값을 구해야 합니다. 따라서 dp를 이용하여 모든 경우를 다 해봐야 합니다. dp식을 어떻게 세워야할지 생각해보면 현재 필요한 정보는 두사람이 바로 직전에 불렀던 음에 대한 정보입니다. 따라서 2차원 dp를 선언한다면 dp[i][j] 가 의미하는 바는 상덕이가 마지막으로 부른 음은 i이고 희원이가 마지막으로 부른 음은j라는 의미입니다. 따라서 dp[i][j]를 통해 점화식을 세우면 ..

https://www.acmicpc.net/problem/7569 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 박스에 익은 토마토가 있을 때 앞뒤좌우상하의 안익은 토마토를 익게 만들어서 모든 토마토가 익는데 걸리는 날을 구하는 문제입니다. 전형적인 bfs 문제이므로 큐를 이용해서 진행해주면 됩니다. 다만 3차원이라서 조금 귀찮은 문제입니다. 다음은 코드입니다. #include #include using namespace std; int tomato[101][101][101]; int nextx[6] = {1, -1, 0, 0, 0, 0}; int nexty[6] = {0, 0, 1, -1, 0, 0}; int nexth[6] = {0, 0, 0, 0, 1, -1}; int ans; st..

https://www.acmicpc.net/problem/16500 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 문자열 S가 주어지고 N개의 줄에 N개의 문자열이 주어질 때 이 N개의 문자열을 이용해서 S를 만들 수 있는지 여부를 판단하는 문제입니다. dp를 이용하여 해결하여야 하는 문제입니다. 1차원 배열 dp를 선언해주고 dp[pos] = pos위치에서부터 남은문자열을 만들 수 있는지 없는지를 의미합니다. 따라서 함수를 하나 선언하고 현재 pos위치에서부터 N개의 문자열중 동일하게 매칭되는 문자열이 있을 경우 위치를 이동하여 계속 진행해 주면 됩니다. 이 문제에서 dp를 이용하는 이유는 문자열을 만들 수 없는지를 체크하는 경우에 dp를 사용하지 않으면 영겁의 시간이 걸리게 됩니다...

https://www.acmicpc.net/problem/14003 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 가장 긴 증가하는 부분 수열의5번째 문제입니다. LIS의 길이와 그 수열을 직접 출력해야 합니다. N이 100만이므로 lower_bound를 이용하여 O(NlogN)의 시간이 걸리는 방법으로 LIS의 길이를 먼저 구합니다. lower_bound를 이용하여 구한 dp배열원소는 실제 수열이 아니므로 실제 수열을 구하기 위해서 pair배열을 하나 둔다음 각각 반복문을 돌때마다 dp배열에서 해당하는 동작을 하는 ind와 그 값을 저장해 줍니다. 이후 pair 배열을 끝에서 부터 역추적하면서 수열을 찾아주면 됩니다. 예를 들어 수열의 길이가 4라면 pair배열의 끝에서부터 확인하며 ind가 3..

https://www.acmicpc.net/problem/8979 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 각 국가의 금메달 은메달 동메달 개수를 입력받고 K국가의 등수를 구하는 문제입니다. 등수를 구하는 기준은 금메달 , 은메달, 동메달이 많은 순서로 우선순위가 정해집니다. 모든 메달의 개수가 동일할 경우 에는 동일 등수로 정해집니다. K국가의 등수를 알고싶다면 K국가보다 등수가 높은 국가들을 단순히 세주기만 하면 될것입니다. 따라서 K국가의 금,은,동메달의 개수를 따로 저장해놓고 전체국가를 돌면서 K국가보다 금,은,동메달의 개수가 더많은 국가들을 세어주면 해결이 됩니다. 다음은 코드입니다. #include using namespace std; struct country { in..

https://www.acmicpc.net/problem/2935 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 10의 제곱꼴로 주어지는 두수를 *나 + 해서 출력하는 문제입니다. *할시에는 두수(문자열)을 더한뒤 첫번째 자리숫자만 1을 출력하고 나머지는 모두 0을 출력 하면 됩니다. +할시에는 더 길이가 긴 문자열의 A.size()-B.size()인덱스에 해당하는 요소를 1로 바꾸어주고 출력하면 됩니다. 두 문자열의 길이가 같을 때는 첫번째 자리숫자를 2로 바꾸어주면 해결이됩니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); strin..