본문 바로가기

Problem/DP

[C/C++] BOJ 1890 :: 점프 BOJ 1890 :: 점프 문제 링크 : https://www.acmicpc.net/problem/1890 자료형의 출력범위를 혼동해서.. unsigned int 로 했다가 틀렸다 ㅠㅠ 한 번에 맞출 수 있었는데... 그래도 문제를 보고 접근방식이 바로 생각났고 생각대로 코딩하여 답을 맞출 수 있어서 매우 뿌듯했다! 나의 풀이 DFS + DP 방식으로 문제 풀기 반환 조건1. 종착역에 도착하면 1 반환2. 이미 dp 배열에 값이 있으면 그 값 반환3. 현재 board의 값이 0 이면 0 반환 반환된 값을 더하여 dp 배열 갱신 ============================================================== 나의 풀이 방법말고 처음부터 끝까지 순차적으로 dp 배열을 채워나가..
[C/C++] BOJ 1103 :: 게임 BOJ 1103 :: 게임 문제 링크 : https://www.acmicpc.net/problem/1103 DFS + DP 방식으로 문제를 풀었다! 나는 두 가지 처리를 못해서 혼자 힘으로 풀지 못했다.. 1) dp 배열 안에 저장된 값이 있을 때 그것을 이용하기.값이 있으면 바로 그 값을 return 해 주면 되는데 이 부분을 고려하지 않았다. 2) count하는 부분.난 dfs의 인자로 count를 주어서 풀이하려고 했는데 계속 틀렸습니다. 가 떴다.결과적으로 인자를 제외하고 코드를 변형시켰더니 맞았는데 이 부분은 내가 자세하게 파고들어서 왜 틀렸는지 알아내야 한다.. 아직 잘 모르겠다. 원래는 이 부분이 // 범위를 넘어갈 때 if (x = N || y = M) return 0; // 구멍에 빠질 ..
[C/C++] BOJ 14925 :: 목장 건설하기 BOJ 14925 :: 목장 건설하기 문제 링크 : https://www.acmicpc.net/problem/14925 나는 왜 BFS 로 하면 풀 수 있을 것이라고 계속 생각했을까 ㅠㅠ?1000*1000에 (V+E)만큼 탐색해야 하는 것을 알고 있었지만.. 예외 처리를 많이 해주면 되는 건줄 알고 bfs에서 빠져나오지 못해 계속 시간초과가 나왔다 ㅠ 하다하다 안되어서 결국 이 문제를 푸는 알고리즘을 찾아보았는데 다이나믹 프로그래밍으로 푸는 것이었다.!!!!!! 배열을 처음부터 끝까지 한 번 돌려야 한다는 것을!!! 왜 생각을 못했을까!!!!!!!! 알고나니 빨리 풀렸다.. 흑 나의 풀이 1. 시작 행과 시작 열의 땅에 목장을 세울 수 있다면 1을 저장, 세울 수 없다면 0을 저장한다. 2. 현재 땅이 ..
[C/C++] BOJ 11727 :: 2×n 타일링 2 BOJ 11727 :: 2×n 타일링 2 문제 링크 : https://www.acmicpc.net/problem/11727 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11727/BOJ_11727.cpp 123456789101112131415161718192021222324252627// 백준알고리즘 11727번 :: 2×n 타일링 2#includeusing namespace std; int dp[1001];int n; int main(){ int n; int tmp = 0; cin >> n; dp[1] = 1; for (int i = 2; i
[C/C++] BOJ 11726 :: 2×n 타일링 BOJ 11726 :: 2×n 타일링 문제 링크 : https://www.acmicpc.net/problem/11726 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11726/BOJ_11726.cpp 12345678910111213141516171819202122// 백준알고리즘 11726번 :: 2×n 타일링#includeusing namespace std; int N;int dp[1001];int main(){ cin >> N; dp[1] = 1; dp[2] = 2; for (int i = 3; i
[C/C++] BOJ 2193 :: 이친수 BOJ 2193 :: 이친수 문제 링크 : https://www.acmicpc.net/problem/2193 다이나믹 프로그래밍으로 푸는 기본 문제이다. 풀이를 위한 그림 설명! 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_2193/BOJ_2193.cpp 12345678910111213141516171819202122// 백준알고리즘 2193번 :: 이#includeusing namespace std; int N;long long dp[91];int main(){ cin >> N; dp[1] = 1; dp[2] = 1; for (int i = 3; i
[C/C++] BOJ 9095 :: 1, 2, 3 더하기 BOJ 9095 :: 1, 2, 3 더하기 문제 링크 : https://www.acmicpc.net/problem/9095 다이나믹 프로그래밍을 이용한 기본 문제이다. 쉬운 이해를 위한 그림 설명! 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_9095/BOJ_9095.cpp 1234567891011121314151617181920212223242526#includeusing namespace std; int dp[10]; int main(void){ int T, data; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i > T; while (..
[백준알고리즘] 11660번 구간 합 구하기5 https://www.acmicpc.net/problem/11660 시간 초과 혹시나 나올까봐 scanf, printf 로 풀었다! https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11660/BOJ_11660.cpp 1234567891011121314151617181920212223242526272829#define _CRT_SECURE_NO_WARNINGS#includeint psum[1025][1025];int main(void){ int N, M, i,j, sx, sy, ex ,ey, val = 0; scanf("%d %d", &N, &M); for (i = 1; i

티스토리툴바