1일1알

한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 수 있다는 것이다. 점화식을 세우기 위한 과정을 우선 top-down 방식으로 생각해 보면 이런 식으로 그려볼 수 있다. 설명을 해보자면, 루트는 우리가 최종 구해야 할 답이고, N개의 카드를 최대한의 가격으로 구매할 때의 가격이다. 왼쪽으로 나눠진 부분은 4번 카드팩을 구매했을때의 상태이다. 4번 카드팩을 구매해서 카드의 개수가 4만큼 줄어들어서 0이 되었고, 카드팩은 구매했다고 사라지는게 아니기 때문에 사용가능한 카드팩은 그대로인 모습이다. 그리고 구매한 카드팩의 가격을 더해준 것이다. 오른쪽으로 나눠진 부분은 4..

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고 아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다. 문제에도 비어있어야 할 칸이 색으로 칠해져있다. 나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; str..

간단한 브루트포스 문제이다. 모든 칸을 돌면서 오른쪽, 아래쪽으로만 검사하면서 정사각형이 되는지 확인하고 크기가 커질때마다 크기를 갱신해주었다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; string str; vector v(n, vector(m)); for (int i = 0; i >..

bfs로 풀 수 있는 문제인데 특이한 점은 가장 빠른 시간만 구하는 게 아니라 그 방법이 몇 가지인지까지 구해야 한다. 최초 도달했을 때 시간을 구하고 그 시간과 같은 시간에 도착 할때마다 Count를 증가시켜주면 된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector visited(100001, false)..

bfs로 문제를 해결하였다. 초기 cnt=1 처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다. 같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lo..

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다. 예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다. (2,2)부터 (3,4) 까지의 합은 이 부분의 합을 구하면 되기 때문에 dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다. 이것을 코드로 나타내면 #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin...

그래프, 트리 관련 문제이다. 우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다. 노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다. 하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다. 2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다. vector[1] : 4, 6 vector[2] : 4 .... 이런식으로 만들었다. 우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..

다이나믹 프로그래밍 bottom-up 방식으로 풀 수 있는 문제이다. 우선 두 가지 경우가 있다. 1. 왼쪽 위에서 시작하는 경우 2. 왼쪽 아래에서 시작하는 경우 1번의 경우를 예를 들어 살펴보면 한 칸 떨어진 대각선을 선택하는 경우와 두 칸 떨어진 대각선을 선택하는 경우로 나눌 수 있다. 다른 어떤 곳을 선택하더라도 결국 이 두 가지로 나뉜다. (100을 선택: 50->50->100, 20을 선택: 50->50->20 or 50->70->20, 10을 선택: 50->50->100->10) 위 경우들을 살펴보면 결국 위의 두 가지의 경우들의 조합으로 만든 선택임을 알 수 있다. 마지막 스티커까지 도달했을 때 1번의 경우와 2번의 경우 중 큰 값이 답이 된다. max(dp[0][n], dp[1][n]) ..

#include #include #include #include #include #include #include using namespace std; int main() { int a, b, c; int arr[3]; while (1) { cin >> a >> b >> c; //while문 종료 if (a == 0 && b == 0 && c == 0) break; arr[0] = a; arr[1] = b; arr[2] = c; //오름차순 정렬 sort(arr, arr + 3); if (arr[0] * arr[0] + arr[1] * arr[1] == arr[2] * arr[2]) { cout

#include #include #include #include #include #include using namespace std; int main() { int x, y, w, h; int min = 1001; cin >> x >> y >> w >> h; //x좌표 비교 (0에서 x까지의 거리와 w에서 x까지의 거리) if (x > w - x) { if (w - x h - y) { if (h - y < min) { min = h - y; } } else { if (y < min) { min = y; } } //네 개의..