노는 게 제일 좋아

//첫번째 풀이 2021.06.07 //두번째 풀이 2022.02.08 //세번째 풀이 2022.06.13 얘도 모든 걸 다 뒤져봐야 하는 문제다. 다만 모든 걸 뒤질 때 어떻게 뒤지느냐가 문제다. 백트래킹, DFS를 사용했다고 보면 된다. https://www.acmicpc.net/submit/14888/29858716 #맞는 풀이 #include #include #define MAX 1000000000 using namespace std; int N; int num[12]; int oper[4]; // {add, sub, mul, div 순} //최대 최소 int m = MAX; int M = -MAX; //백트래킹 이용같다. //입력은 현재까지의 연산결과를 받고 사용한 연산자 개수도 입력받는다 vo..

어렵지 않지만 예외가 있었다. 바로.. 같은 용액이 쓰이면 안된다는 것이었다. 처음에 나는 두번째 가까운 원소까지 찾을 생각은 안했었다. 하지만 모든 것이 알칼리성이나 산성으로 되었을 때는.. 두 번째로 가까운 원소가 필요해졌다. https://www.acmicpc.net/problem/2470 #맞은 풀이 #include using namespace std; //두 용액 더한 값 범위 int로 가능 int N; int liq[100000]; vector ans; //해당 액체의 숫자에 (-1) 곱한 것과 가장 가까운 원소를 찾아야함 //즉, x와 일치하거나 가장 가까운 원소를 return함. int bisearch(int input){ int x = -input; //우리가 찾아야하는 값. int l ..

이것도 아주 중요한 문제라고 할 수 있다. 중복되는 값을 어떻게 골라내느냐이다. https://www.acmicpc.net/problem/1039 #맞은 풀이 #include #include #include #include using namespace std; int N, M, K; int ans; set check[11]; //★★★★★★★ void func(string s, int cnt) { string after = s; int x = stoi(s); //string으로 받은 숫자. //K번 바꿨을 때. if (cnt == K) { ans = max(x, ans); return; } //바꿀 수 있는 모든 경우의수 확인 for (int i = 0; i < M - 1; i++) { for (int ..

백트래킹에서 그래도 조건이 많이 붙어서 가지치기를 어떻게 하는지 공부할 만한 문제다. 행과 열 처리는 어떻게든 가능하지만 3*3이 어느 칸인지 찾는 것을 조금 고민해볼 필요는 있다. 결국 1~3까지 첫 째 4~6까지 두 번째.. 이렇게 생각하면 어떻게 할 지 감이 온다. https://www.acmicpc.net/problem/2580 #맞은 풀이 #include #include using namespace std; int pane[9][9]; // 9*9 게임판 bool check = false; // 답을 찾았는지 체크 vector vec; // 채워야 할 곳의 좌표 int number = 0; // 채워야 할 곳의 개수 //조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를..

백트래킹 중에 가장 중요한게 시간인데 백트래킹을 가지치기해서 최대한 시간을 줄여야한다. 왜냐하면.. 백트랙킹은 가짓수가 기하급수적으로 늘어난다. 싹수가 노랗다면 없애야하듯이 가지쳐야한다. https://www.acmicpc.net/problem/15686 #맞은 풀이 #include using namespace std; const int MAX = 51; int N, M; // int node[MAX][MAX]; int ans = INT_MAX; vector chicken; vector house; bool checked[51][51]; vector chosen; //idx가 있는 이유. 이미 골라본 것은 다시 고르지 않음. void func(int cnt, int idx){ if(cnt == M){ /..

이거 왜 이렇게 풀었지?라고 생각했는데 진짜 이렇게 풀려서 당황했다. 나는.. 진짜 플레를 풀 줄 몰랐다. 근데 그냥 이렇게 풀면되지 않을까? 했는데 풀렸다. 난이도 내려야할 듯하다. 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일차까지 경로가 수정된..

어렵지 않았다. 다만 머리로 아 어떡하지? 중복제거 어떡하지?? set 생각날 때까지 어려웠다. https://www.acmicpc.net/problem/5568 #맞은 풀이 #include using namespace std; int n,k; set numbers; vector card; bool check[10]; //카드를 고르면서 정수를 만듬. void func(int cnt, string s){ if(cnt == k){ numbers.insert(stoi(s)); //1,3 과 13은 자리를 바꿔도 같은 정수라 중복 제거해야함. //set 이용 return; } for(int i=0; i> n >> k; for(int i=0; i> x; card.push_back(x); } func(0,"");..

indexed tree로 풀었다. 하지만 어떤 이유로 indexed tree로 풀었느냐..? Indexed tree는 해당 숫자가 많은데 update가 자주될 때.. 사용하는 것 같다. 난 그랬다. https://www.acmicpc.net/problem/2243 #맞은 풀이 #include using namespace std; int idx_tree[1 단말 노드에 100만개를 넣어야하기 때문. int n; int base;// 단말 노드의 처음 idx값 //p번째 맛의 캔디의 개수를 v만큼 바꾸는 것. void update(int p, long long v) { p += (base - 1); //base - 1을 하는 이유는 B가 1부터 시작하기 때문(0번째 idx를 제외하고 숫자시작) idx_tre..

어렵지 않았다. 그냥 시키는대로만 했다. 다만... tuple을 사용할 때는.. 직접 접근이 아니면 값복사라는 사실을 간과하고 짰다.. 30분 날렸다. ㅎ https://www.acmicpc.net/problem/1713 #맞은 풀이 #include #include #include #include using namespace std; vector frame; int N; int student; bool cmp(tuple& t1, tuple& t2) { if (get(t1) == get(t2)) { if (get(t1) == get(t2)) return get(t1) > get(t2); else return get(t1) < get(t2); } return get(t1) < get(t2); } int ma..

어려웠다. 우선순위 큐를 이렇게 이용한다는 것이 나에겐 조금 어려웠다. 시간을 보아하니 절대로 Brute Force, 전수조사는 아니었다. 힌트를 보고나서야 풀 수 있었다. https://www.acmicpc.net/problem/1655 #맞는 풀이 #include #include using namespace std; int N; priority_queue minH; priority_queue maxH; int main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> N; for(int i = 1; i> x; //min에 넣을지 max에 넣을지?? //한쪽에만 몰아넣으면 안된다. //그렇게 하면 중간값을 바로 알 수 없어서 둘의 사이즈를 항상 차이가 1만큼만 나게 해..