문제https://www.acmicpc.net/problem/9177시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 dfs + dp로 풀었다. 첫번째 단어를 a, 두번째를 b, 세번째를 c라고 하자. c의 첫번째 글자은 a의 첫번째 글자이거나, b의 첫번째 글자일 것이다. 둘다일수도 있다. 현재 사용된 이 알파벳이 a일때와 b일때를 구분해서 계속 dfs로 들어가면서, 최종적으로 c를 만들 수 있는지를 판단한다. dfs를 하면서 지금 사용해야하는 a와 b, c의 인덱스를 인자로 넘겨준다. 이때, 재귀를 하면서 a, b의 같은 인덱스를 여러번 탐색할 수도 있다. 예를 들어, 다른 탐색에서 a와 b의 인덱스가 각각 1, 2일때 불가능함을 알았을때, 다른 경로로 1, 2에 다시 왔다면, 볼 이..
문제https://www.acmicpc.net/problem/15663시간 제한메모리 제한solved.ac 티어1초512MB실버 2풀이 며칠만인지 모르겠지만 아무튼 오랜만에 밀린 문제 정리하기다. 이번 N과 M은 원소를 조합으로 뽑는 문제이다. 언제나 그렇듯 사전 기준 오름차순 출력이기 때문에 입력받은 N개의 원소를 정렬한 후, 백트래킹으로 M개의 숫자를 중복없이(같은 인덱스의 원소를 뽑지 않고) 뽑는다. 이때 N개의 원소에는 중복되는 원소가 존재할 수 있다. 이를 모두 고르게 되면 중복되는 수열이 등장하게 된다. 이를 방지하기 위해 map에 출력한 output과 해당 값이 출력되었는지 기록하여, 중복된 수열이 나오더라도 출력은 한번만 되도록 했다.코드#include #define ALL(X) X.be..
문제https://www.acmicpc.net/problem/17253시간 제한메모리 제한solved.ac 티어1초256MB17252번 (삼삼한 수) : 실버 417253번 (삼삼한 수2) : 실버 3풀이 사실 삼삼한 수 2를 먼저 풀고나서 삼삼한 수 1을 검색해봤는데 N의 최댓값이 훨씬 적어서 삼삼한 수 2의 코드를 그대로 복붙해서 제출했다. 따라서 필자는 삼삼한 수 2를 기준으로 설명할 것이다. 이 문제는 그리디하게 풀이할 수 있다. 풀이 순서는 다음과 같다.n에 가장 근접하면서 n이하의 3의 거듭제곱 3^k = a를 찾는다.(n - a) = n'와 k - 1을 인자로 재귀함수에 넘겨준다. 같은 3의 거듭제곱은 사용할 수 없기 때문에 k - 1을 넘긴다.최종적으로 재귀함수에 넘어온 n'값이 0이 되..
문제https://www.acmicpc.net/problem/17609시간 제한메모리 제한solved.ac 티어1초(추가 시간 없음)512MB골드 5풀이 밀린 문제이다. 일반적인 회문은 원래 문자와 뒤집은 문자가 같은 것을 의미하지만, 해당 문제에서는 유사 회문이라는 개념을 제시한다. 유사회문이란 원래 회문은 아니지만 문자를 단 한개를 지웠을 때 회문이 되는 문자를 의미한다. 이 문제에서는 어떤 문자가 회문인지, 유사회문인지, 그것도 아닌지 모두 판단해보는 문제이다. 일반적인 회문 판단은 풀이할 필요가 없을 듯하니, 코드를 바로 읽어보면 될 것 같다. 우리가 중요하게 봐야하는건 유사회문 판별이다. 일반적인 회문처럼 문자열의 맨 앞과 맨 뒤를 검사하되, 중간에서 다른 문자를 만날수도 있을 것이다. 하지만..
문제https://www.acmicpc.net/problem/12919시간 제한메모리 제한solved.ac 티어2초512MB골드 5풀이 밀린 문제 정리다. 이 문제도 역발상이 중요한 문제이다. S->T로 가는 것이 어렵다면, 그 역방향으로도 갈 수 있는지 생각하는 유연함이 필요하다. 저번 16953번(https://codejin.tistory.com/268)에서도 반대 방향으로 역추적하는 방식을 사용하는 풀이를 보이기도 했었다. 이런 발상을 바로 할 수 있도록 연습을 더 해야겠다. 이 문제는 어떻게 역추적을 하는지 생각해보자. 문제에서 말하는 연산을 위에서부터 각각 a, b연산이라고 간단하게 부르기로 하자. S->T로 가기 위해서는 a작업을 할수도 있고, b작업을 할 수도 있다. 당연히 모든 경우의 수..
문제https://www.acmicpc.net/problem/15652시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이 역시 백트래킹 문제이다. 다만 이전에 풀었던 15650번 N과 M(2)과 비슷한 문제이다. 비내림차순이라는 단어가 나와서 내림차순이 아닌 상태의 수열을 출력하라는줄 알고 순간 놀랐지만, 오름차순이라는 말을 굳이 꼬아서 쓴 것이었다. 해당 문제는 중복을 허용하기 때문에 15650번과는 다르게 반복문의 범위를 이전에 선택한 값도 다시 선택할 수 있도록 했다.코드#include #define endl '\n'using namespace std;int n, m;void sol(int prev, int cnt, string output) { if (cnt == m) { cout..
문제https://www.acmicpc.net/problem/15650 시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하..
