Mini

14497번: 주난의 난(難) (acmicpc.net) 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net * 어려우면 1차원에서 해보면서 논리를 짜라 # 1 0 0 1 0 0 계속 //q.push 1->멈춰, cnt++ //temp.push, q=temp, cnt++ ex) next가 1일때, temp.push만 되므로 q.size==0이 됨 => q=temp, cnt++ 실행됨. //새로운시작 * bfs는 도중에 탈출X, 방문배열에 정답을 모두담고, 출력만해라. * 탈출조건 문제 while (true..

12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net * 정답 경우의수 구하기 핵심코드 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next >= 0 && next >k ; /* * bfs algorithm * 1.초기화 cnt[n] = 1; * 2.종료조건 * 3.next 범위체크 * 4.next 방문체크 * 5.visit[next] 갱신 * 5.1 q.push!..

13913번: 숨바꼭질 4 (acmicpc.net) 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net * bfs 경로추적 핵심코드 prev[10]=5 // prev[5]=3 .. 이런식으로 연결함. ex) 노드 : 5-10-11(목표k) 벡터 : 11(k)-10(prev[11]). 문제 : 첫노드는 안들어감 ,역순으로 넣어짐 해결 : push(start), 리버스 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next..

12869번: 뮤탈리스크 (acmicpc.net) 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net /* * bfs algorithm * 1.초기화 * 2.종료조건 * 3.next * 4.next 방문체크 * 5.visit[next] 갱신 */ *핵심로직 1. visit[체력][체력][체력] = 최단거리(공격횟수) 1.1 idx에 각각 체력저장. 2.v[0][0][0] 에 방문했다? -> bfs이므로 -> 최초 체력 0,0,0으로 만든애가 최단거리임. -> 출력. 끝. #include using namespace std;..

16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net * dfs 조건처리는 contine만으로 가능, 빡구현필요X if (abs(a[y][x] - a[ny][nx]) r) continue; * for(v) 조건문실행되면 연결할게 있었다는 뜻 -> ret++, else break 조건문안에 flag=1 => 연결할게잇는지없는지 검사 !flag 이면, 종료. for (pair p : v) { a[..

4179번: 불! (acmicpc.net) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net *팁 bfs는 main안에서 짜는게 낫다. ret는 전역변수로? * 아이디어 1. 불bfs => 불 도착시간들 모두 저장 2. 사람bfs : 종료조건 -> 그때v값이 답임. ---------------------------------- 불보다 visit이 작다 -> 더빨리도착가능 -> 이동가능. == visit(불) >= 사람 -> continue; *예외처리 불이없는경우? visit(불) : 0 0 0..

15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net *로직 1. 완탐? 13C6 * 50 * 13 ok 2.for(13Cm) for (home) for(치킨) min갱신,ret갱신 * 조합핵심코드 /* * * 조합함수 암기 * * 결과 : idx 조합결과 * chichenList[0] -> [0,1] * chichenList[1] -> [0,2] * chichenList[2] -> [1,2] */ void combi(int start, vect..

https://www.acmicpc.net/problem/1325 > n>>m ; for (int i = 0; i > a>>b; adj[b].push_back(a); } //디버깅 /*for (int i = 1; i