노는 게 제일 좋아

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

이 문제는 쉬웠지만 시간초과가 나는 이유를 간과했다. 분명 순서가 쓸모 없음에도.. 나는 순서를 고려하여 세지 않아도 되는 경우의 수까지 고려해서 시간 초과가 난 것이다. 그냥 무지성 백트래킹을 박아버렸다. https://www.acmicpc.net/problem/16922 #맞은 풀이 #include using namespace std; set counts; vector vec = {1,5,10,50}; // 최대 카운트, 현재 카운트, 현재 문자, 결과합 void func(int maxi, int cnt, int idx, int res){ if(cnt >= maxi){ counts.insert(res); return; } //문자의 순서는 상관없으므로 각 문자의 개수만 고려한다. //1번문자 a개 2..

전형적인 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;// 충분히 큰 ..

브루트포스지만 식이 잘 생각이 안난다. 솔직히 어떻게 풀어야겠다라고 생각을 해야 모든 케이스를 뒤지는건데 그렇지 않으면 풀지 못한다. 이 리모컨은.. 1. 그냥 돌리는게 더 빠르잖아? 2. 번호를 누르는게 더 빠르잖아? 3. 번호를 우선 누르고 그 뒤에 돌리는게 빠르잖아? 위 3가지를 고려해야한다. 100 - 101은 그냥 버튼 하나만 누르면 되는 거고 그런 식이다. https://www.acmicpc.net/problem/1107 #맞은 풀이 #include using namespace std; bool button[10]; //false //해당 채널로 이동하기 위한 숫자입력 횟수 int possible(int n){ //0번 채널로 이동하는 경우 if(n == 0){ //고장나면 숫자로 이동 불가능..

실수하기 쉬운 문제고 나도 실수했다. 그리고 처음부터 생각하기는 쉽지 않다. 비트마스킹으로 풀만한 문제였다. 2^10 = 1024 https://www.acmicpc.net/problem/2800ㄴ 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net #맞은 풀이 #include using namespace std; //괄호를 "한 쌍"씩 뺀 경우, 집어넣은 경우 => 모든 경우해야할듯 int maxNum = 0; stack pos; vector pairPos; set answer;..

이 문제는 스택에 관한 예외처리를 하는데 도움이 된다. 순서를 잘 생각해야 하는 문제다. 대충 답을 끼워맞춘 느낌이고 코드가 정제되지 않았지만 이런 식으로 푸는 듯 하다. https://www.acmicpc.net/problem/17413 #맞은 풀이 #include using namespace std; stack stk; string s; int main(){ //띄어쓰기 포함 모든 문자열을 받아야함 getline(cin, s); bool isTagging = false; //Tagging 중일 때, 아닐 때 //공백을 만났을 때, 아닐 때 for(char c : s){ if(c == ''){ cout

이것도 재밌고 문제로 나오지 않을까? 싶다. https://www.acmicpc.net/problem/2146 #맞은 풀이 #include using namespace std; #define X first #define Y second int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N; int conti[100][100]; int area[100][100]; int dist[100][100]; int flag = 1; int minDist = INT_MAX; void DFS(int x, int y){ area[x][y] = flag; for(int dir = 0; dir= N || ny = N)continue; if(area[nx][ny]..