https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 입력으로 주어진 수들로 만들 수 있는 최대 수를 구하는 문제입니다. 다만 입력으로 주어진 모든 수를 사용해야하며 중복으로 고를 수 있습니다. k개의 수와 n개의 택을 할 때 어떻게든 가장 큰 수를 뽑기 위해서는 가장 큰 수를 최대한 많이 골라 이어 붙혀야 합니다. ex. 1, 23, 456 / 5개 택 => 456 23 1 1 1 < 456 456 456 23 1 또한 10..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP 응용 문제입니다. 입력 받은 문자열에서 겹치는 것을 허용하였을 때 2번 이상 검색되는 부분문자열의 최대 길이를 구하는 문제입니다. 전형적인 KMP 알고리즘의 경우 1번 나오면 탐색을 종료하거나 모든 위치를 파악하는데 주로 쓰이지만, 2번의 카운트를 해주는 조건을 추가하면 됩니다. 문자열의 처음부터 구할 수 있는 최대 길이 (2번 이상 카운트 된) 를 m..
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 값을 ..