완전탐색으로 푸는 문제다 이렇게 문제가 길면 어렵운것보다 눈에 잘 안들어와서 큰일이다 계속 다 풀어놓고 변수명 틀리고 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..
java를 이용해서 문제를 풀어봤다 먼저 모든 방법의 수는 4^10이므로 2^20이랑 같고 완탐으로 충분히 가능하기 때문에 모든 경우의 수를 돌려봤다 4방향을 한번씩 가면서 dfs를 이용하면 된다 방향을 정한 다음에는 R > B > R 순서대로 공을 굴려봤다 R을 두번 굴리는 이유는 R이 B 뒤에있어서 B에 막힌다면 B가 움직이고 똑같은 거리만큼 더 가야하기 때문에 한번 더 보내보는 경우다 근데 답을 체크해주는 부분을 함수에서 잘못 설정해서 모든 경우를 못봤다 그래서 틀렸다..!!! 복잡할수록 천천히 신중하게 코드를 짜야겠다..! 소스코드 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 ..
완전탐색을 통해 찾을 수 있는 문제다 모든 단어는 antc로 시작하고 tica로 끝나므로 최소 antic 문자는 배워야한다! 5개!! 그럼 알파벳 21개중에 내가 k-5개를 골라서 그 알파벳들로 최대로 배울 수 있는 문장수를 찾으면 된다! 비트를 통해 알파벳을 고르고 하나하나 확인해보자! 소스코드 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 #include #include #include #include using namespace std; int n,k,ans;..
백트래킹을 이용해 풀 수 있는 문제다! 근데 막풀면 틀린다 처음에 그냥 있는그대로 넣고 구하고 생각해보니 시간이 20^10이였다 ㅋㅋㅋ 구간의합의 부호를 주기 때문에 수를 고르고 구간의 합을 확인 후 가능하면 넘기면 된다! 근데 헷갈리는 부분은 같은 수를 중복으로 못쓰는 줄 알았는데 사용가능하다..! 중복으로 사용 못하게 풀면 틀린다! 소스코드 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 #include using namespace std; int n; char op[12][12]; int psum[12],ans[12]; bool check(int..
유명한 N-Queen 문제다! 백트래킹을 통해 찾을 수 있다 여기서 핵심은 내가 한 행을 기준으로 보면 된다는 것이다 그럼 한 행을 잡고 그 안에서 퀸을 놓을 수 있는 열을 찾고 다음 행으로 가는 것이다 그렇게 행을 끝까지 도착하면 경우의수가 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 #include using namespace std; int n,ans; bool check[22][22]; int dx[2] = {-1,-1}; int dy[2] = {-1,1}; bool inner(int x,int y)..
순열을 이용해 해결할 수 있는 문제다 기억해야할건 순열을 쓰기전에 정렬시키고 사용해야 한다는 것! 그걸 잊고있다가 오랜시간이 걸렸당.. 사용되는 알파벳을 찾아두고 순열로 점수를 매겨서 최댓값을 찾아보면 된다! 소스코드 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 #include #include #include #include #include using namespace std; int n; int a[11],b[111]; bool c[30]; string sa[11]; int main(){ scanf(" %d",&n); for(int i=0;i>sa[i]; ..