노는 게 제일 좋아

백트래킹 중에 가장 중요한게 시간인데 백트래킹을 가지치기해서 최대한 시간을 줄여야한다. 왜냐하면.. 백트랙킹은 가짓수가 기하급수적으로 늘어난다. 싹수가 노랗다면 없애야하듯이 가지쳐야한다. 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만큼만 나게 해..

시간초과가 왜 난지 몰랐지만.. 그냥 나중에 생각해보니 날만했었다. 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; //만약 모르는 글자가 나오..

사실 어렵다기보다는 생각이 어렵다. 구현은 어렵지 않다. 솔직히 힌트를 얻어서 했지만.. 과연 내가 혼자서 할 수 있을까?? 는 고민이다. https://www.acmicpc.net/problem/2842 #맞은 풀이 #include #include #include //distance를 쓰기 위함 #include using namespace std; const int MAX = 51; const int INF = 987654321; char pos[MAX][MAX]; int height[MAX][MAX]; int visited[MAX][MAX]; int dr[8] = { -1,-1,-1,0,0,1,1,1 }; int dc[8] = { -1,0,1,-1,1,-1,0,1 }; set h; int N; int..

DP는 항상 봐도 이해하고 나야 쉽지..그 전엔 어렵다 https://www.acmicpc.net/problem/1103 #맞은 풀이 #include #include #include using namespace std; const int MAX = 51; int r, c; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int ans = 0; //최대 동전 움직인 횟수. bool chkInf = false; int map[MAX][MAX]; int visited[MAX][MAX]; //int finished[MAX][MAX]; int dp[MAX][MAX]; //cr,cc는 위치를 위함 cnt는 동전 움직인 횟수를 위함. void DFS(int cr, int ..

물론 이것도 DP 문제다. 왜냐하면.. 경우의 수가 무지막지하게 늘어나기 때문이다. 이런 실버 1문제를 1시간이나 걸리다니... 예외를 찾는게 너무 오래걸렸다. https://www.acmicpc.net/problem/2011 #맞은 풀이 #include #include #include using namespace std; const int DIV = 1000000; string s; long long dp[5001]; int num[5001]; int main() { cin >> s; int length = s.size(); long long ans; //1부터 시작하게 바꿈. for (int i = 0; i < length; i++) { num[i + 1] = s[i] - '0'; //문자열이므로 i..