노는 게 제일 좋아

이것은 그냥 생각했을 때.. 단순한 문제지만 시간을 단축하려면 조금 더 머리가 필요한 문제였다. 중요한 문제라고 생각한다. 우선순위 큐라면 이 문제가 가장 대표적이라고 생각한다. 나는 시간초과나서 실패했다. 그리고 다시 답을 찾게되었다. https://www.acmicpc.net/problem/1826 #시간 초과 풀이 #include using namespace std; //해당 위치의 값이 0이 아니면 주유소의 위치이며 값은 기름의 양임 int stations[1000001]; //이렇게 하면.. 시간 초과남, 답은 나올지 모르겠으나 풀이는 아님 int N; int ans = 123456789; int l,p; //도착위치, 초기 기름양 void func(int pos, int cnt, int fue..

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

은근히.. 헷갈렸다. 사실 쉬웠는데.. 헷갈렸다. 짜증난다 ㅠㅠㅠ 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 = ..

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