https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 오랜만에 알고리즘 문제를 풀었습니다 ㅎㅎ 이제 자기 전에 한 문제씩 다시 풀어야겠습니다... 길이 연결되어 있는 상황에서 길을 건너지 않고는 못 만나는 소가 몇 쌍인지 구하는 문제입니다. 반대로 생각하면 전체 경우인 kC2 에서 길을 안 건너고 만날 수 있는 경우를 빼면 됩니다. 조합으로 구하기 위해 소 번호는 자신보다 큰 소를 만날 때만 카운트합니다. ..
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 인 것이고, 이는 ..