노는 게 제일 좋아

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; } ..

어렵지 않았다. 다만 귀찮아서 힘들었다. 구현문제는 역시 뭔가 힘들다. https://www.acmicpc.net/problem/2174 #맞은 풀이 #include using namespace std; struct Robot{ int x; int y; int dir; int number; }; //N (0,1) : 0 S(0,-1) : 1 //W (-1,0) : 2 E(1,0) : 3 int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int board[101][101]; //로봇의 위치 0(없음) 나머지 숫자(있음) bool isError; int main(){ int A,B; cin >> A >> B; int N,M; cin >> N >> M; vector robo..

사실 그냥 이렇게 배치하면 무조건 최소로 될 것이다.라는 감이와서 한 것인데.. 은근히 시간 오래걸렸다. https://www.acmicpc.net/problem/11497 #맞은 풀이 #include using namespace std; //이웃하는 통나무의 최대 차이가 가장 적게 나는 배치 순서 // | x1 - x2 | 가 가장 작아야 한다. => 원형으로 배치되어있음 //통나무 개수는 10000개까지임 // 5개가 있다고 할 때 아래처럼 배치해야함. 즉, 첫번째를 중심으로 양쪽에 작은것부터 넣는다. // 1 // 2 3 // 4 5 //덱을 이용하겠다. int main(){ int test; cin >> test; while(test--){ int num; cin >> num; vector log..

우선 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 = ..

BFS 중에서 가장 재밌는 유형이면서 가장 까다롭다. 조건이 별로 없어서 다행이지.. 여러개면 진짜 한없이 어려워진다. 가장 중요한 문제가 아닌가 싶다. 이 문제를 잘 풀줄 알면.. 다른 것도 잘풀 걸..? https://www.acmicpc.net/problem/5427 #맞는 풀이 #include using namespace std; int dc[4] = {-1,1,0,0}; int dr[4] = {0,0,-1,1}; char board[1002][1002]; int test[1002][1002]; //불 위치, 0 빈공간, -1 불이 갈 수 없는 공간 int live[1002][1002]; //상근이 탈출 int main(){ int testcase; cin >> testcase; //맵이 크기 상..

전형적인 브루트포스 문제지만 당연히 시간을 줄이는 방법이 있었다.누적합을 이용하는 것이다.★★★★★★ 누적합에 대해선 따로 다시 공부해야겠다. 하지만 바로 생각하지 못해서 오래걸렸다. https://www.acmicpc.net/problem/20002 #맞은 풀이 #include using namespace std; int board[301][301]; long long sum[301][301]; long long ans = INT_MIN; int main(){ int N; cin >> N; for(int i = 1; i board[i][j]; } } //누적 합을 이용한다 => 바로 생각하지 못함...ㅠ for(int i = 1; i

전형적인 백트래킹문제이면서 조건이 많이 달린 문제다. 쉬웠다. https://www.acmicpc.net/problem/16938 #맞은 풀이 #include using namespace std; int N,L,R,X; vector level; //조건 난이도 합 L보다 크거나 같음 // 난이도 합 R보다 작거나 같음 // 난이도 차 X보다 크거나 같음 int ans; void func(int cnt, int idx, int maxi, int mini, int sum){ if(cnt == N){ if(maxi - mini >= X){ if(sum = L){ ans++; } } return; } //i번째 문제를 포함한 것과 아닌 것 for(int i = idx; i> N >> L >> R >> X; fo..

전형적인 BruteForce다. 다만. 10자리라는 숫자는 큰 숫자이기에 나같은 범위를 착각하는 실수를 하지 않기를 바란다. https://www.acmicpc.net/problem/2529 #맞은 풀이 #include using namespace std; int k; vector vec; long long maxN = -9999999999; //범위 조심 string MM; long long minN = 9999999999; //범위 조심 string mm; bool check[10]; bool IsValid(int a, int b, int seq){ if(vec[seq] == '>'){ return a > b; }else{ return a < b; } } void func(int cnt, string..

어렵지 않았다. 다만 어떻게 풀지? 가 관건이다. https://www.acmicpc.net/problem/14226 문제 분석부터 해보자 최솟값을 가지는데 수행해야 하는 작업의 가중치가 같다? BFS 가자 #include using namespace std; //1개는 이미 입력 int S; int visited[3000][3000]; int main(){ cin >> S; //현재 상태, 클립보드에 저장된 개수 queue q; q.push({1,0}); visited[1][0] = 1; while(!q.empty()){ auto cur = q.front(); q.pop(); int now = cur.first; int clip = cur.second; //체크 if(now == S){ cout