https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 간단한 dp 문제였습니다. 알약 하나가 반개로 쪼개져서 조금 햇갈릴 수 있지만, 케이스만 잘 나누면 쉽습니다. dp[w][h] 를 W가 w개, H가 h개 남았을 때라고 하면, 1. H밖에 안 남은 경우, 즉 항상 dp[0][h] = 1 입니다. H밖에 안 남았으니 ...HHHH..HHH 와 같은 경우 밖에 없습니다. 2. W밖에 안 남은 경우 W만 남은 경우, W 중 1개를 먹으면 W는 w-1개, H 1개가 됩니..
https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 처음에 dfs로 접근했다가 단순히 클립보드에 내용을 복사하는 경우에서 시간만 카운트시켜야하는데 파라미터 조정을 생각하기가 조금 까다로웠습니다. 그래서 bfs로 문제를 조금 바꿔 풀었습니다. (큐에 넣는 내용이나 파라미터에 넣는 내용이나 비슷하지만 처음에 1차원 배열 dp랑 섞어서 풀다보니 바꾸기가 음 좀 그랬다......) 큐의 원소로는 화면 개수, 클립보드 개수, 시간 이렇게 3개의 int 값을 ..
https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 주어진 입력이 처음에 어떤 수열인지 판단하는 문제입니다. 규칙은 간단합니다. x 부터 시작해 x가 3의 배수이면 3으로 나눌 수 있고, x가 어떤 수든 2를 곱할 수 있습니다. 3을 나누고 2를 곱하는 규칙 밖에 없으므로 배열에서 중복된 값이 나올 수는 없습니다. 왜냐하면 x 를 기준으로 y가 되었는데 x = y 라고 한다면 (x / 3^n) * 2^m = y 인 것이고, 이는 ..
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS를 이용해 퍼즐을 풀 수 있습니다. 0의 위치를 기준으로 BFS를 돌리면 됩니다. 하지만 메모리가 아주 작기 때문에 배열이 아닌 string을 활용해 map의 키로 활용하여 해당 string이 조회되었는지 확인합니다. 코드는 다음과 같습니다. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; /..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 그래프가 주어져 있을 때 최소 스패닝 트리 (MST) 를 만드는 문제입니다. 전체 간선을 오름차순으로 정렬 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리를 만들면 됩니다. 크루스칼 알고리즘을 이용해 MST를 만들면 모든 마을을 이을 수 있는 최소 경로를 찾을 수 있게 되고 이 때 마지막 가중치를 가지는 간선 (연결 가능한 간선 중 가중치 최대) 인 것을 빼면..