Algorithm/🏫assignment18 # Driving License # 문제 # 입력 및 출력 # 풀이 어처피 회전 횟수를 제외하면 세로 M-1, 가로 N-1칸씩 이동하는 것은 정해져 있다. 따라서 L * {(M-1) + (N-1)}은 고정이고 여기에 회전 횟수만 최소로 해서 더해주면 결과 값을 구할 수 있다. 문제는 연료이다. 주어진 연료 G 이하로 사용하면서 회전 횟수를 최소로 만들어야 한다. 처음엔 pair을 사용해서 하려다가 너무 복잡해지기도 하고 접근이 힘들어져서 4차원 배열을 선택했다. dp[x][y][k][l] => (x, y) 좌표에서 회전수가 k번이고, 방향은 l일 때의 최소 연료 합 일단 (x,y) 좌표에서 회전수는 max(x, y) * 2를 절대 넘지 않는다. 예) (2,2) 에서는 최대 3번, (2,4) 에서는 최대 4번, (3,3) 에서는 최대 5.. 2022. 11. 14. # MST # 문제 # 입력 및 출력 # 풀이 kruskal 알고리즘은 슈도 코드를 참고해서 쉽게 해결했는데 prim 알고리즘은 슈도 코드를 보고 해결하기가 힘들었다 그래서 dfs 방식을 생각했다 원래 사용하던 큐 대신 우선순위 큐를 사용해서 가중치 값이 같을 경우 edge number가 빠른 순서대로 정렬하고 이것을 사용해서 dfs 방식으로 조회하도록 했다 처음 prim 알고리즘을 슈도 코드대로 코드를 짰다가 프로그램이 터졌었는데 dfs로 푸니까 해결됐다 #include #include #include #include using namespace std; ifstream fin("mst.inp"); ofstream fout("mst.out"); vector e; // (edge number,(w,(u,v))) v.. 2022. 11. 9. # Adding Ways # 문제 # 입력 및 출력 # 풀이 dp[i][j] = dp[i-1][j-1] + dp[i-j][j] 점화식은 위와 같다. 왜 이렇게 되는지 예를 들어 설명해보자 예) (n, k) = (5, 3) 일 때 5를 3개의 자연수로 나타내는 방법은 1. 1이 들어가는 경우 2. 1이 들어가지 않는 경우 이렇게 나눌 수 있다. 1이 들어가는 경우엔 1 + (4를 2개의 자연수로 나타내는 방법) 이 되기 때문에 dp[i-1][j-1] 식이 오게 된다. 1이 들어가지 않는 경우엔 j가지 방법으로 나눌 때 1은 무조건 하나씩 기본으로 놓고, 최소 2가 되어야 하기 때문에 1씩 주고 남은 i-j개를 j가지로 나누어주면 된다. #include #define MOD 1000000007; using namespace std;.. 2022. 10. 31. # Card Game # 문제 # 입력 및 출력 # 풀이 처음에 풀 땐 dp[i][j]를 만들어서 i부터 j까지의 카드중에서 맨 앞과 맨 뒤 중 어떤 값을 선택할지를 dp에 저장해뒀었다. 근데 이렇게 하면 문제점이 가장 큰 값을 선택하기 때문에 앞에 작은 값이 오더라도 계산 결과는 크게 나오는 경우를 처리하지 못했다. // 틀린 코드 #include #include using namespace std; ifstream fin("card.inp"); ofstream fout("card.out"); int card[1000]; pair dp[1000][1000]; int cal_sum(int n, int fb) { int s, e, sum; if (fb == 0) { s = 1; e = n - 1; sum = card[0]; }.. 2022. 10. 29. # 카드 선택 # 문제 # 입력 및 출력 # 풀이 입력 예를 dp로 풀어보았다. 처음에는 1차원 dp를 썼는데 조건문이 너무 들어가는데다가 너무 어려워져서 다른 방법을 생각했다. 그래서 i-4를 선택하는 경우, i-3을 선택하는 경우, i-2를 선택하는 경우로 나눠서 풀었다. i번째 카드를 선택하고 이전에 선택한 카드가 i-4번째 카드인 경우, i-3번째 카드인 경우, i-2번째 카드인 경우 중에서 가장 큰 것을 선택해서 푸는 방법이다. 편의를 위해 인덱스의 0번은 전부 사용하지 않았다. 그래서 인덱스 1번부터 3번까지는 이전에 선택할 카드가 따로 없기 때문에 dp에 a[i]만 그대로 넣어준다. 인덱스가 4번일땐 i-4번째 카드는 선택할 수 없기 때문에 INF 값을 넣어줘서 max 비교 시 문제가 없도록 설정해줬다. .. 2022. 10. 8. # 정육면체 # 문제 # 입력 및 출력 # 풀이 뭔가 간단해보이는데 어려웠다. 규칙을 좀 찾으려고 하나하나 풀어보다가 발견했다. 처음엔 점화식을 아래와 같이 잡았다. min({ dp[x / 2][y][z] + dp[x / 2 + x % 2][y][z], dp[x][y / 2][z] + dp[x][y / 2 + y % 2][z], dp[x][y][z / 2] + dp[x][y][z / 2 + z % 2] }) 이렇게 잡은 이유는 size를 5로 놓고 계산했을 때 1, 4의 합이나 2, 3의 합이 같았기 때문에 그냥 접근하기 쉬우려고 절반을 사용했다. 이렇게 하니까 문제가 하나 발생했다. (2,2,5) 값을 구할 때를 예를 들어보자. (2,2,2) 와 같은 케이스는 =(1,1,1) 이라 (2,1,2) + (2,1,2) .. 2022. 10. 7. 이전 1 2 3 다음
