혼종 꼬지마루
이 문제는 저도 참고하고 풀었습니다 처음 접근은 크기가 40밖에 되지 않아서 정렬하고 구간으로 나누어 S가 되는 것을 카운팅 했으나 -10 3 10의 경우 S가 0일때 답은 1, 하지만 제가 푼 방법으로는 0이 나왔기에 잘못됬다는 것을 알았습니다. 이 문제를 해결하기 위해서 먼저 배열을 양쪽으로 나누어 나올 수 있는 모든 합의 경우의 수를 L, R로 나누어 저장 그리고 나서 L에서의 하나의 값과 R에서 나오는 값이 합이 S가 되는 갯수를 세어주면 됬습니다. 하지만 N = 40일 경우 각각 경우의 수가 1048575개 씩 나오기 때문에 모두 비교하기 보다는, 두개의 합이 S가 되는 시작점, S보다 커지는 시작점을 R에서 찾아서 그 위치의 차를 더해주었습니다. 12345678910111213141516171..
전형적인 DP문제 입력을 받으며 DP배열의 (r - 1, c), (r, c - 1), (r - 1, c - 1) 중 가장 큰값을 현재 입력되는 위치의 사탕개수를 더해주면 끝 123456789101112131415161718192021#include #define MXSIZE 1002#define MAX(X, Y) (X) > (Y) ? (X) : (Y)using namespace std; int map[MXSIZE][MXSIZE], dp[MXSIZE][MXSIZE];int N, M; int main(void){ cin >> N >> M; for (int i = 1; i map[i][j]; dp[i][j] = MAX(dp[i - 1][j - 1], MAX(dp[i - 1][j], dp[i][j - 1]));..
테트로미노를 두개 놓고 최대값을 구하는 문제 이 문제 그냥 8개까지 놓고 생각하면 19*500*500*19*500*500의 시간이 걸린다...결론은 말도 안되는 범위 그렇기 때문에 먼저 한개를 놓았을 때 최대가 되는 걸 찾고, 그다음에 놓는 걸 생각하기로 했다 하지만 이렇게 하면, 문제가 되는게 max값이 같은것이 여러개일 경우 모두 따져 주지 못한다 그렇기 때문에 max값이 갱신될때 마다 그 위치를 구조체 배열을 선언해서 후보값들을 넣어준다 이렇게 되면 19*500*500 + 19*500*500*a까지 줄어들면서 문제를 해결할 수 있다 이렇게 해도 어마무시하게 시간이 걸릴 줄 알았는데 464ms로 생각보다 빠르게 구할 수 있었다 12345678910111213141516171819202122232425..