노는 게 제일 좋아

투 포인터 좋은 예라고 볼 수 있다. 여기서 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일차까지 경로가 수정된..

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만큼만 나게 해..

시간초과가 왜 난지 몰랐지만.. 그냥 나중에 생각해보니 날만했었다. https://www.acmicpc.net/problem/1062 #맞은 풀이 #include #include #include #include using namespace std; bool alpha[26]; int N, K; vector vec; int ans = 0; //idx를 추가시켜서 시간을 단축 시켰다. //여기서 idx는 for문이 시작하는 번호를 말한다. void func(int cnt, int idx) { //K-5개만큼 골랐다면 if (cnt == K-5) { int cnt = 0; //각 단어를 읽을 수 있는지 조사 for (string str : vec){ bool read = true; //만약 모르는 글자가 나오..