노는 게 제일 좋아

솔직히 바로 생각을 못했다. 값을 다 계산해야하나? 싶었다. 하지만 힌트를 보고야 말았으니.. 즉, 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/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 중에서 하다보면 규칙을 찾는 것이다. 규칙을 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부터 시작하므로 나머지에 대한 계..

처음부터 생각하기는 힘들다. 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가 더..

DFS + DP 문제다. DFS를 어떻게 설계해야할까? 가 문제다. https://www.acmicpc.net/problem/1937 #맞는 풀이 #include #include #define X first #define Y second using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int map[500][500]; int dp[500][500]; int N; int ans; //좌표 int dfs(int x, int y) { //만약 저장되어있지 않으면 if(dp[x][y] == 0){ dp[x][y] = 1; // 우선 해당 노드에서 1일 살 수 있음( + 방문체크와 같음) int cnt = 0; // 몇개나 다른 노..

음.. 생각은 빨리했는데.. 오래걸림.. 왜냐면.. 초기화를 잘못했다. 아...내 1시간반 https://www.acmicpc.net/problem/14502 그렇게 어렵지 않았다. 벽을 무작위로 세워야 하는 것을 이미 알기에.. Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다. 가장 처음 제출한 풀이.. #include #include #include #define X first #define Y second using namespace std; int map[8][8]; int visited[8][8]; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int ans = 64; stack stk; // DFS 스택 ve..