노는 게 제일 좋아

//첫번째 풀이 2021.12.05 //두번째 풀이 2022.02.08 어렵다기보다는.. 조건이 많은 문제였다. https://www.acmicpc.net/problem/1759 #맞은 풀이 #include #include #include using namespace std; int L, C; vector vec; bool isUsed[15]; //L,C는 글로벌, 백트래킹함수 -> 차례대로 고름 void func(int cnt, string s) { //L개 골랐다면 출력할지 정함 -> 자음 2개 모음 1개 if (cnt == L) { int consonant = 0; int vowel = 0; for (int i = 0; i < L; i++) { if (s[i] == 'a' || s[i] == 'e'..

//첫번째 풀이 2021.05.26 //두번째 풀이 2022.02.08 이 문제도 백트래킹이지만 조금 꼬아서 냈다. 출력을 조금 더 어렵게했다. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 내가 접근했던 틀린 풀이부터 보자 #include #include using namespace std; void init() { ios::sync_with_stdio(0); cin.tie(0); } int a, b..

//첫번째 풀이 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..

투 포인터 좋은 예라고 볼 수 있다. 여기서 R의 예외조건에 대해서 알아야하는데 내가 짠 알고리즘에서는 R이 커져버려서 while문에 다시 못들어가는데 있었다. https://www.acmicpc.net/problem/16472 #맞은 풀이 #include using namespace std; int N; string s; map kind; int ans = 0; // 최대 구간 길이 int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>N; cin>>s; int num = 0; // 종류 int L = 0; int R = 0; if(s.size()

어렵지 않지만 예외가 있었다. 바로.. 같은 용액이 쓰이면 안된다는 것이었다. 처음에 나는 두번째 가까운 원소까지 찾을 생각은 안했었다. 하지만 모든 것이 알칼리성이나 산성으로 되었을 때는.. 두 번째로 가까운 원소가 필요해졌다. 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,"");..