완전탐색으로 푸는 문제다 이렇게 문제가 길면 어렵운것보다 눈에 잘 안들어와서 큰일이다 계속 다 풀어놓고 변수명 틀리고 0,1 틀리고 실수가 많다! 집중해서 한번에 확 푸는 연습좀 해야겠다 이 문제는 톱니바퀴를 직접 굴릴 필요는 없고 그냥 2,6번째를 r,l 이라는 화살표로 본다고 생각하고 화살표를 움직이면 된다! 그럼 마지막에 화살표가 움직인 거리만큼 0에서 움직여보면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #incl..
숨바꼭질? 그 문제랑 비슷한 문제다 내가 갈 수 있는 경우를 다 큐에 넣고 bfs를 돌리면 된다 이 때 시간마다 칸이 사라지므로 그 경우를 큐의 사이즈를 통해 해결하자! 평소처럼 큐가 비어있으면 돌리는게 아닌 현재 시간에 갈 수 있는 만큼만 큐를 돌리는거다 현재 시간에 움직일 수 있는 칸 == 현재 큐 사이즈 이용 ㄱㄱ 문제를 잘 읽어보면 N번 칸 보다 더 큰 칸으로 간다면 1이므로 조건을 잘 확인하자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ..
dp 문제다 테이블을 잡을 때 d[n][k]로 잡았다 숫자 n을 만들 때 마지막 수가 k인 경우의 수다 그럼 이 테이블을 사용해서 계속 채워나갈 수 있다 중복이 없다고했으니 우리는 정렬했다고 가정하고 마지막수가 가장 큰 수라고 생각하자 그럼 마지막 수가 1,2,3 오는 경우를 생각하면 d[n][2] = d[n-2][1~2]가 된다 왜냐면 마지막에 오는 가장 큰 수는 2이므로 1부터 2까지 보는것이다 아래부터 축적해나가면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int n; int d[10010][4]; int main() { scanf(" %d", &n); d[1][..
90도로 방향을 바꾸기 위해서는 거울이 1개 필요하다 이 때 C -> C까지 갈 때 최소 거울을 찾는 문제다 다익스트라를 이용해서 d[100][100][4]로 각 방향으로 갈 때 최소비용을 구했다 만약 90도 방향이 바뀐다면 그때만 비용을 +1 해줬다 마지막 도착지에서는 4방향 중 가격이 가장 싼 곳을 출력하면 된다 다른 사람들 풀이를보니 그냥 bfs만 돌려도 충분히 풀 수 있다 내가 방향이 바뀌면 새로운 점들을 queue에 비용을 증가시켜 넣고 현재 정점에서는 다시 한칸 앞으로가서 비용없이 또 탐색을 하면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 3..
매일 풀어야지 풀어야지 하다가 안풀고있던 문제다 완전탐색으로 풀 수 있는데 이런 복잡한 구현문제는 확실하게 해야한다 계속 대충대충 생각하고 채점디버깅을 이용하니 반례가 넘처난다..! 최대 4방향 5번이므로 4^5 각각 이동시키는데 최대 20^2 정도 되니까 다 찾아봐도 된다! 이동시키는 move 함수 빼고는 평범하게 모든 경우를 고르는 코드다 move 함수에서는 방향에 따라 x,y좌표를 잡고 앞에있는 숫자부터 숫자를 옮기고 숫자가 합쳐졌는지 check배열을 통해 확인한다 그래서 숫자가 가다가 check=false인 같은 수를 만나면 합치고 check=true로 바꿔주자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..