문제 설명DP 문제입니다. 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.제한 사항풀이  전체 코드#include #include using namespace std;const int MAX = 1000001;int N;int DP[MAX];int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; DP[1] = 0; for (int i = 2; i 횟수만 구하는 문제였으면 위와같이 작..

문제 설명DP 문제입니다. 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.제한 사항풀이 DP[i] = max(DP[i], DP[1...i-1] + Arr[i]);전체 코드#include #include using namespace std;const int MAX = 1001;int N;int DP[MAX];int Arr[MAX];int main() { ios::sync_with_stdio(false); ci..

문제 설명DP 문제입니다. 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.제한 사항 풀이DP[i-1]에 2*1타일 붙이는 경우 + DP[i-2]에 2*2 타일 붙이는 경우따라서 DP[i] = DP[i-1] + DP[i-2]. 전체 코드#include using namespace std;const int MAX = 1001;int N;int DP[MAX];int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; DP[1] = 1; DP[2] = 2; for(int i=3; i

멀티 쓰레드 환경?: 일반적인 STL Container 문법은 멀티 쓰레드 환경에서 동작하지 않음1. vector : 메모리 동적할당 방식. 1. 문제 : 멀티 스레드 환경에서는 순서가 보장되지 않아, 메모리 공간을 삭제하거나 옮기는 과정에서 crash 발생, 메모리 손실 발생2. 해결법1 : vector.reserve()를 사용하면 메모리 공간을 삭제하거나 옮기는 일이 발생하지 않아서 crash는 나지 않지만, 메모리 손실 발생 3. 해결법2 : Lock사용2. volatile : 컴파일러에게 최적화를 하지 말아달라고 부탁int32 a = 0;a=1; a=2; a=3; a=4; cout : Debug모드가 아닌 Release모드(최적화 진행)로 빌드하면 a = 4만 남게 됨 volatile 키워드를 추..

문제 설명DP 문제입니다.돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 제한 사항풀이N이 3의 배수일 때(3, 6, 9)에는 DP[i] = DP[i-3] + 1이고, 그렇지 않다면 DP[i] = DP[i-1] + 1 이 된다.  전체 코드#include using namespace std;const int MAX = 1001;int N;int DP[MAX];int main() { ios::sync_with_stdio(fal..

문제 설명DFS + DP 문제입니다.여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로..

문제 설명DP 문제입니다.어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다.이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 제한 사항풀이  전체 코드#include using namespace std;const int MAX = 100001..

문제 설명DP 문제입니다.n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 제한 사항풀이  전체 코드#include using namespace std;const int MAX = 10001;int N, K;int DP[MAX] = {0, };int Coin[101] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> K; for(int i=1; i> Coin[i]; ..

문제 설명DP 문제입니다.3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 제한 사항풀이  전체 코드 #include using namespace std;const int MAX = 31;int N;int DP[MAX] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; DP[0] = 1; DP[2] = 3; if(N%2 == 1) { cout

문제 설명DP 문제입니다.0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 제한 사항풀이 전체 코드 #include using namespace std;const int MAX = 201;int N, K;int DP[MAX][MAX] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> K; for(int j=0; j