노는 게 제일 좋아

이전의 1학년 문제와 같다. 다만 경우의 수를 고려하는 것이 아닌 그냥 최댓값이 무엇이냐?라는 것이다. 그래서 솔직히 BFS로 풀어볼까도 생각했었다. 결국 N번째 도착지만 알면 되니까..? 아무튼 근데 그냥 DP로 풀었다. 점화식이 조금 더 직관적이어서 그랬다. https://www.acmicpc.net/problem/1495 #맞은 풀이 #include #include using namespace std; int N, S, M; int arr[52]; int dp[52][1001]; //dp[i][j]는 i번째에 볼륨 j를 가질 수 있는지 여부(-1, 1); int main() { cin >> N >> S >> M; //N개의 곡 입력받음.(첫번째 곡은 주어졌고 N번의 볼륨을 변화시켜야함 //총 N+1..

솔직히 바로 생각을 못했다. 값을 다 계산해야하나? 싶었다. 하지만 힌트를 보고야 말았으니.. 즉, N개의 수에서 N-1번만 조사하면 되는 것이고 N-1까지의 경우의 수를 구하려면..? N-2에서 N-1번째 원소를 더하거 나 빼는 경우를 세어주면 되었다. https://www.acmicpc.net/problem/5557 #맞은 풀이 #include using namespace std; int N; int arr[101]; long long dp[101][21]; //N번째에 K값이 나오는 경우의 수 int main(){ long long ans; //답의 범위가 2^63-1임 cin >> N; for(int i =1; i> arr[i]; } int target = arr[N]; //초기값 dp[1][ar..

처음에 감을 못잡았는데.. N-1번째에 사자를 놓느냐 마느냐를 집중했어야 했는데 사자가 1마리 일때, 사자가 2마리 일때, 사자가 3마리 일때의 규칙을 찾으려니까 못찾았다. 나의 실수다. 시간제한을 보니 2초다. 또한 최소 100,000개의 배치를 해야한다. 배열로 만들지 고민했다. https://www.acmicpc.net/problem/1309 #맞는 풀이 #include using namespace std; int N; const int MAX = 100001; int dp[MAX][3]; //120만 바이트 -> 1.2메가정도 int main(){ cin >> N; dp[1][0] = 1; //1번째 줄에 아무것도 놓지 않는 경우 dp[1][1] = 1; //1번째 줄에 왼쪽에 사자를 놓는 경우 ..

증가수열과 비슷하다. 여기서 전깃줄이 겹칠 때 어떨 때 겹칠까 생각해보면 된다. https://www.acmicpc.net/problem/2565 #맞은 풀이 #include #include #include using namespace std; //A가 내가 고르는 것 B가 결과라고 해보자 //내가 고른 것이 이전에 고른 것의 결과보다 작아선 안된다. //다음 것은 내가 고른 것의 결과보다 항상 커야한다. //1번줄을 연결해서 2번줄의 결과를 얻었다면 //2번줄을 연결했을 때 2번보다 작은 결과를 얻어서는 안된다. //내가 순서대로 고르고 결과만 위의 조건에 맞게 하면 되겠다. //-> 전깃줄 순서대로 정렬 //전깃줄을 삭제하는 방법이 아닌 최대의 전깃줄 연결 방법 //-> 최대 5개의 전깃줄을 연결할 ..

증가수열을 어떻게 구하는지 알면 바로 푼다. 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

항상 N번째 일때는 어떻게 해야 가장 길어질까? 이전의 어느 원소를 가져와야할까?? 생각을 해보자 https://www.acmicpc.net/problem/11053 #맞는 풀이 #include #include using namespace std; const int MAX = 1001; int N; int arr[MAX]; int dp[MAX]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> x; arr[i] = x; } //초기값 fill(dp, dp+1001, 1); //자기자신은 항상 포함되므로 최소 1 for(int i = 1; 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부터 시작하므로 나머지에 대한 계..