노는 게 제일 좋아

전형적인 백트래킹문제이면서 조건이 많이 달린 문제다. 쉬웠다. 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]..

처음에 조금 헷갈렸다. 어렵진 않지만 헷갈리기 쉽다. https://www.acmicpc.net/problem/1245 #맞은 풀이 #include using namespace std; int dx[8] = {-1,-1,-1,0,0,1,1,1}; int dy[8] = {1,0,-1,1,-1,1,0,-1}; int mount[101][101]; bool visited[101][101]; int N,M; bool isPeak; int cnt = 0; //이름만 DFS지 그냥 재귀를 이용한 것 void DFS(int x, int y){ for(int dir = 0; dir=N || ny = M)continue; //나보다 큰 봉우리라면 탐색이 끝났을 때. false가 되어있으므로 봉우리 아..

어렵진 않지만 실수할 경우가 많은 문제가 아닌가 싶다. https://www.acmicpc.net/submit/14225/44550103 #맞은 풀이 #include using namespace std; int N; vector vec; unordered_map dict; //그냥 숫자체크 void func(int cnt, int result){ if(cnt == N){ //cout N; for(int i = 0; i> x; vec.push_back(x); } func(0,0); long long num = 1; while(true){ if(dict[num] == 0){ cout

쉬운 문제다. 백트래킹의 전형적인 형태를 보여준다. https://www.acmicpc.net/problem/6603 #맞은 풀이 #include using namespace std; vector vec; //6개 뽑으면 종료 => 조건 사전순, 조합, 현재까지 뽑은 결과 void func(int cnt, vector result, int cur){ if(cnt == 6){ for(auto c : result){ cout