Algorithm/🏫assignment18 # Coin Game # 문제 # 입력 및 출력 # 풀이 이 풀이가 맞는진 모르겠는데 그냥 전부 내가 모든 케이스를 찾아보았다. 병에서 4단위로 모든 케이스가 반복된다. 주어진 조건에선 따로 병의 순서는 정해주지 않았기 때문에 1 0 0 의 케이스든 0 1 0 의 케이스든 답은 모두 동일하게 나온다. 따라서 dp[4][4][4]를 선언해놓고 -1이 되는 케이스를 따로 지정해줬다. 1) 0 0 1 2) 0 2 2 3) 0 3 3 4) 1 1 1 5) 1 2 3 위 케이스의 경우에만 -1이 되고 나머진 전부 1이 된다. 앞서 말했듯이 순서는 상관이 없기 때문에 조건문을 편하게 사용하기 위해 정렬을 해줬다. sort(check, check+3, less()); 이 부분에서 처음에 less()를 사용했다가 컴파일 에러가 났다. 찾아.. 2022. 10. 1. # 격자 경로 # 문제 # 입력 및 출력 # 풀이 find_min_cost 함수는 최소 비용을 찾는 함수 find_path 함수는 최소 비용 경로의 좌표를 결과 스택에 저장하는 함수 grid[200][200]은 입력되는 비용을 저장할 배열 dp[200][200]은 현재 좌표까지의 최소 비용을 저장할 배열 stack result는 최소 비용 경로의 좌표를 저장할 스택 queue q는 경로 탐색을 위한 큐 MAX 987654321 은 -1대신 사용하기 위해 선언 find_min_cost 함수를 통해 dp[N-1][M-1] 값이 MAX가 되면 경로가 없는 것이므로 No path. 출력 #include #include #include #include #define MAX 987654321 using namespace std;.. 2022. 9. 30. # Bitmap # 문제 # 입력 및 출력 # 풀이 처음엔 재귀를 돌 때 size로 돌게 했었다. 근데 시간초과가 뜨길래 조건문을 걸어서 필요한 부분만 보면 되나 했지만 출력을 위해선 전부 돌아야 하기 때문에 문제가 없어 보였다. 그래서 일단 재귀함수의 파라미터를 size가 아닌 인덱스 값으로 주고 start x, start y, end x, end y 값을 사용해서 돌도록 했다. 해당 문제가 백준에도 있어서 백준에서 먼저 문제를 풀었다. 근데 백준에서는 맞는 답이 espa에서 돌리니까 시간 초과가 떴다. 그래서 fstream 관련해서 시간 초과 문제가 있는지 찾아봤다. 중요한 점 fstream을 사용했는데 해당 파일 입출력 라이브러리가 cstdio 라이브러리의 파일 입출력보다 시간이 매우 많이 걸린다. 그래서 fstr.. 2022. 9. 26. # 순열을 이진트리로 # 문제 # 입력 및 출력 # 풀이 분할 정복으로 풀면 된다. pair p[1000] 은 순열의 수와 depth를 쌍으로 저장할 배열 visit[1000]은 해당 순열을 트리에 넣었는지 확인하는 배열 find_max_idx(int s, int e) 함수는 p배열의 index s ~ e 범위에서 가장 큰 값이 있는 인덱스를 리턴 rec(int s, int e, depth) 함수는 재귀적으로 돌면서 트리의 depth를 구하는 함수로 이미 트리에 있는 숫자가 들어오면 리턴 #include using namespace std; ifstream fin("permutation.inp"); ofstream fout("permutation.out"); pair p[1000]; int visit[1000]; int T,.. 2022. 9. 23. # 격자 색칠 # 문제 # 입력 및 출력 # 풀이 일단 해당 조건을 만족하기 위해선 가로든 세로든 같은 색으로 2줄 이상 칠해져야 한다. 그래서 2줄 이상 칠해져야 한다는 조건을 만족하기 위해 일단 2줄씩은 무조건 색칠하도록 했다. 그래서 사용한 배열이 cnt 배열이다. 같은 줄을 몇 줄이나 칠할 수 있는 지 세는 배열이다. 같은 줄을 2줄 이상 칠할 수 있는 경우엔 2줄씩 먼저 색칠하고 그 다음에도 색칠을 다 못한 경우가 있을 땐 2줄보다 더 많이 칠할 수 있는 색으로 전부 색칠하면 된다. 색을 칠할 때 2줄 이상이 되면 홀수가 되든 짝수가 되든 상관이 없기 때문이다. 말이 좀 헷갈리는데 6줄을 칠해야 하는 경우라면 1. 2-2-2 2. 2-4 3. 3-3 이런 방법으로 색칠할 수 있다. 처음 코딩할 땐 3번의 경우.. 2022. 9. 18. # 달팽이 # 문제 # 입력 및 출력 # 풀이 처음에 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1, 1 이 값을 빼주는 작업이 시간 초과가 걸릴 것이라고 생각했다. 왜냐하면 N이 10^7으로 매우 큰 상태기 때문이다. 근데 막상 보면 N^2번 반복되는 작업이 아니고 N번 반복되는 작업이기 때문에 시간초과는 걸리지 않는다. 엄청 복잡하게 풀어서 알고리즘을 천천히 글로 정리해봤다. 글로 쓰고 나니까 머릿속에 정리가 되는 느낌이다. #include using namespace std; long long N; long long dx[4] = { 0,1,0,-1 }; long long dy[4] = { 1,0,-1,0 }; ifstream fin("snail.inp"); ofstream fout("sn.. 2022. 9. 16. 이전 1 2 3 다음
