노는 게 제일 좋아

DFS + DP 문제다. 나는.. DP를 까먹고 있어서 답을 결국 봐버렸다.ㅠㅠ 어쩐지.. 이 문제는 중요해보였다. 아니 우선 나에게 통찰력을 주었다. https://www.acmicpc.net/submit/12869/48753292 #맞은 풀이 #include using namespace std; //재귀만 해보려는데 도저히 생각이 안나서...답을 찾았다. int dp[61][61][61]; //DP를 사용하라는데.. 재귀 + DP란다. //scv 체력 a,b,c에 대해서 각 공격을 적용해본다. int func(int a, int b, int c){ //죽은 scv에 대해서는 연산하지 않는다. //이 처리를 하는 이유는 음수에 대한 계산을 하지 않기 때문이다. if(a> N; //배열 모두 초기화 me..

BFS + DP 문제다. 사실 DP란 것은 아니고.. 그냥 상태 저장문제라고 보면 된다. 즉, 이전의 작은 값을 보장하면 그것들의 합이 최소라는 것에 대해선 DP라고 볼 수 있다. https://www.acmicpc.net/problem/4485 #맞은 풀이 #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int cave[126][126]; int main(){ int cnt = 0; while(1){ cnt++; int n; cin >> n; if(n == 0)break; int dp[126][126]; //행:r 열:c for(int r = 0; r cave[r][c]; dp[r][c] = INT_MAX; } ..

은근히.. 헷갈렸다. 사실 쉬웠는데.. 헷갈렸다. 짜증난다 ㅠㅠㅠ BFS문제면서 DP 문제라고 생각하면 되겠다. https://www.acmicpc.net/problem/16928 #맞은 풀이 #include using namespace std; vector fromTo; //보드 int dist[101]; //array[출발]=도착 int arr[101]; int main(){ int N, M; cin >> N >> M; for(int i = 0; i> start >> finish; arr[start] = finish; } //배열초기화(시작주소, 종료주소(얼만큼 할지), 값) fill(dist, dist+101, -1); //1부터 BFS로 시작 dist[1] = 0; queue q; q.push(1..

우선 DP문제인줄 알고 풀었고 메모리도 적당히 딱 맞는듯해서 그렇게 풀었지만 의도는 다른 것이라고 한다. 슬라이딩 윈도우라고 하는데..? 음.. 투포인터랑 비슷하다고 한다. 슬라이딩 윈도우도 또 한 번 글을 써야 겠다. https://www.acmicpc.net/problem/2096 #맞은 풀이 #include using namespace std; int arr[3]; int dpmin[3]; int dpmax[3]; int main(){ int n; cin >> n; //가장 처음 줄 cin >>arr[0] >> arr[1] >> arr[2]; //초기화 for(int i = 0; i now0 >> now1 >> now2; //dpmax값이 변하기 전값을 가지고 있어야함 int tempMax_0 = ..

전형적인 DP 문제다. 다만 조건을 곁들인? DP인 것을 쉽게 파악하였으나 조건을 만족시키려면 어떻게 해야하는가를 좀 많이 고민했다. 결국 하나씩 3개 돌리는 것이 답이었다. https://www.acmicpc.net/problem/17404 #맞는 풀이 #include #define R 0 #define G 1 #define B 2 using namespace std; const int MAX = 1002; int cost[MAX][3]; int house[MAX][3]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int num; cin >> num; for(int i = 1; i cost[i][j]; } int ans = 123456789;// 충분히 큰 ..

처음엔 어려웠다. 왜냐면.. 나는 이전 것의 결과만 생각했다. 즉, [3] 을 구하기 위해서는 [1] 과 [2]의 사칙연산만 하면 되는 줄 알았으나.. 교환법칙이 성립하지 않는 '/' 나눗셈과 '-' 때문에... [2]와 [1]도 계산해야했다. 나는 그것을 몰라서.. 다 틀렸다. https://programmers.co.kr/learn/courses/30/lessons/42895 #맞는 풀이 #include using namespace std; int solution(int N, int number) { int answer = -1; vector vec(10); vec[1].push_back(N); // 문자 한개 쓰인 것 추가. if(number == N) return 1; int seq = 2; wh..

이거 왜 이렇게 풀었지?라고 생각했는데 진짜 이렇게 풀려서 당황했다. 나는.. 진짜 플레를 풀 줄 몰랐다. 근데 그냥 이렇게 풀면되지 않을까? 했는데 풀렸다. 난이도 내려야할 듯하다. https://www.acmicpc.net/problem/5573 #맞은 풀이 #include using namespace std; //1: 오른쪽 0: 아래쪽 const int MAX = 1003; int H,W,N; //세로, 가로, N번째 일 int road[MAX][MAX]; int dp[MAX][MAX]; //N일까지 해당 위치를 지나간 횟수 int main(){ cin >> H >> W >> N; for(int i=1; i road[i][j]; } } //어느 위치에서 종료하느냐? //N-1일차까지 경로가 수정된..

DP는 항상 봐도 이해하고 나야 쉽지..그 전엔 어렵다 https://www.acmicpc.net/problem/1103 #맞은 풀이 #include #include #include using namespace std; const int MAX = 51; int r, c; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int ans = 0; //최대 동전 움직인 횟수. bool chkInf = false; int map[MAX][MAX]; int visited[MAX][MAX]; //int finished[MAX][MAX]; int dp[MAX][MAX]; //cr,cc는 위치를 위함 cnt는 동전 움직인 횟수를 위함. void DFS(int cr, int ..

물론 이것도 DP 문제다. 왜냐하면.. 경우의 수가 무지막지하게 늘어나기 때문이다. 이런 실버 1문제를 1시간이나 걸리다니... 예외를 찾는게 너무 오래걸렸다. https://www.acmicpc.net/problem/2011 #맞은 풀이 #include #include #include using namespace std; const int DIV = 1000000; string s; long long dp[5001]; int num[5001]; int main() { cin >> s; int length = s.size(); long long ans; //1부터 시작하게 바꿈. for (int i = 0; i < length; i++) { num[i + 1] = s[i] - '0'; //문자열이므로 i..

이전의 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..