노는 게 제일 좋아

증가수열을 어떻게 구하는지 알면 바로 푼다. https://www.acmicpc.net/problem/11054 #맞은 풀이 #include #include using namespace std; const int MAX = 1001; int N; int arr[MAX]; int dp[2][MAX];//0번째 정방향, 1번째 역방향 증가수열. int main(){ cin >> N; fill(dp[0], dp[0]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐 fill(dp[1], dp[1]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐 for(int i = 1; i> arr[i]; } //dp[0][N]은 N번째 원소를 마지막으로 하는 증가 수열의 길이를 말함 for..

이것 내가 현재 칸에 있다면 어떤 칸을 거쳐서 오는 것이 좋은가? 어느 칸에서 올 수 있는가? 현재 칸을 오면 사탕개수가 어떻게 되는가? 를 생각하자 https://www.acmicpc.net/problem/11048 #맞는 풀이 #include #include using namespace std; const int MAX = 1001; int N, M; int map[MAX][MAX]; int dp[MAX][MAX]; int main() { cin >> N >> M; for (int i = 1; i map[i][j]; } } //초기 값 1행과 1열 값 초기화 (0행, 0열의 성분은 0임) dp[1][1] = map[1][1]; //1행 for (int i = 2; i

이 문제도 DP다. 과연 N번째 동전은 어느 것을 가져와야할까?를 생각해보자 N-1번째 동전은 무엇을 쓰는 것이 좋을까 생각해보자 https://www.acmicpc.net/problem/2294 #맞는 풀이 #include #include #include using namespace std; const int MAX = 10001; int N,K; int dp[MAX]; vector vec; int main(){ cin >> N >> K; fill(dp, dp+10001, MAX); //우선 min에 걸리지 않게 충분히 크게 MAX로 초기화 for(int i = 0; i> x; vec.push_back(x); if(x>10000)continue; //어차피 K보다 가치가 큰 동전은 쓰지 않음 dp[x]..

DP 중에서 하다보면 규칙을 찾는 것이다. 규칙을 2분만에 찾아서 바로 풀 수 있었다. 하지만 잘 보이지 않는다면.. 조금 힘들다. 항상 N-1과 N의 관계를 생각하면 될 것 같다. https://www.acmicpc.net/problem/11057 #맞는 풀이 #include using namespace std; int dp[1001][10]; int N; int main(){ cin >> N; //초기값 for(int i = 0; i

감이 안잡히면 가장 어려운게 DP가 아닐까.. 이것도 그렇다. https://www.acmicpc.net/problem/1915 #맞는 풀이 #include #include #include #include using namespace std; int n, m; int map[1001][1001]; int main() { cin >> n >> m; //최솟값 int ans = 0; for (int i = 0; i > s; for (int j = 0; j < m; j++) { map[i][j] = s[j] - '0'; //만약 1이 등장하면 최소 ans = 1 if (map[i][j] == 1) ans = 1; } } //1,1부터 시작하므로 나머지에 대한 계..

플로이드 알고리즘 적용해서 풀었다. 크리스마스 쉬고와서 그런지.. 머리가 하나도 안돌아간다. https://www.acmicpc.net/problem/1389 #맞는 풀이 #include #include #include #include #define INF 123456789 using namespace std; int cost[105][105]; int N,M; int main(){ cin >> N >> M; for(int i = 1; i from >> to; cost[from][to] = 1; cost[to][from] = 1; } //자기 자신으로 돌아오는 경로도 있어서 초기화 시켜줘야함 최단 경로 0으로 for (int i = 1; i

물론 처음부터 생각은 안나겠지만 가장 DP다운 문제가 아닌가 싶다. 항상 N번째 항을 어떻게 구해야할까 생각하면 DP의 답은 나오지만.. 항상 생각나는 것은 아니다. https://www.acmicpc.net/problem/11055 #맞는 풀이 #include #include using namespace std; int N; int arr[1001]; int dp[1001]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> arr[i]; } //dp[i] -> arr[i]를 증가 부분 수열의 마지막이라 할 때의 부분 수열의 합. //즉, 현재 위치의 값을 더한 것이 dp[i]에 저장됨 //dp[i]채우기 for(int i = 1; i

처음부터 생각하기는 힘들다. DP라는 것을 예상할 수 있지만 점화식을 바로 생각하기는 어렵다. https://www.acmicpc.net/problem/1699 #맞는 풀이 #include #include using namespace std; // 100000을 루트하면 대충 350 이하.. //또한 최소항의 수를 만들기 위해 큰 것부터 집어넣기로함, 그리드 // 그리드로 안풀림..ㅎ dp로 풀어야할 듯. int arr[100001]; int N; int main(){ cin >> N; //모든 N에 대해서 최소항의 개수를 찾아봄 for(int i = 1; i 어떤 제곱수 항을 가져야 최소 개수를 가질지 다 뒤져봄 // -> 그리디는 틀린 방식 18 = 4^2,1^2,1^2 지만 사실 3^2,3^2가 더..

실제로 MST, 최소 신장 트리를 구현하면 된다. 나는 Prim 알고리즘을 썼다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net #맞는 풀이 #include #include #include #define MAX 10005 using namespace std; using ti3 = tuple; int v,e; // 정점, 간선 개수 vector adj[MAX]; //인접 행렬 bool check[M..

문제에서 모든 컴퓨터가 연결되었다. 최소비용이다를 보고 최소신장트리가 생각나면 정답이다. https://www.acmicpc.net/problem/1922 #맞는 풀이 #include #include #include #include #define MAX 1001 using namespace std; using ti3 = tuple; int n,m; vector adj[MAX]; //1000개는 인접행렬로 부담스러움(뭐 1000개까진 괜찮다 사실) //cost, to가 들어갈 예정 bool check[MAX]; //이미 이어져있는지 확인 int Prim(){ int cnt = 0; int tot = 0; priority_queue heap; //1번부터 시작함 for(auto next : adj[1]){ ..