본문 바로가기

Algorithm159

# 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.
# 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.

티스토리툴바