문제https://www.acmicpc.net/problem/23309시간 제한메모리 제한solved.ac 티어2초 (추가 시간 없음)512MB (추가 메모리 없음)골드 4풀이 중앙에서 삭제와 삽입이 빈번하고, 앞 뒤가 이어져 있으며, 하나의 역에서 이전 원소와 다음 원소를 모두 알고 있어야 한다. 이중 원형 연결리스트 문제이다. 하지만 STL의 list를 곧이 곧대로 사용했다가는 TLE가 날 것만 같은 N과 M의 최댓값이다. 그래서 메모리의 손해를 좀 보고, 이차원 배열에 이중 원형 연결리스트의 개념을 접목시켰다. 모든 역에는 고유번호가 붙기 때문에 이 고유번호를 배열의 인덱스로 잡고, 해당 배열에는 각각 이전 역의 고유번호와 다음 역의 고유 번호를 저장하도록 한다. 고유번호는 100만까지 있고, 각 ..
문제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/17451시간 제한메모리 제한solved.ac 티어1초1024MB실버 3풀이 v의 최댓값이 매우 크기 때문에 당장 떠올린 풀이는 이분탐색이었다. 어떤 mid값에서 각 행성의 정수배수로 줄여가면서 최종적으로 행성을 모두 통과할 수 있는지를 구하면 된다. 이때 속도의 최댓값이 10^9이라고 int형을 써선 안된다. 10^9의 정수배도 연산하는 과정에서 들어갈 수 있고, 정답도 10^9 이하라고 한 적은 없기 때문에 이분탐색의 최댓값과 자료형에 주의해야한다. log(long long의 최댓값) ≒ 18이기에 적당히 10^18을 최댓값으로 사용했다. 어짜피 이분탐색을 하면 최댓값을 저렇게 줘도 연산은 70번을 넘지 않으니 넉넉하게 잡았다.코드#incl..
문제https://www.acmicpc.net/problem/25955시간 제한메모리 제한solved.ac 티어1초512MB실버 4풀이 오늘은 개인적으로 일이 바빠서 실버문제 한문제만 풀고 정리하려고 한다. 정렬문제이다. 랜덤으로 뽑았는데 이게 나왔다. 정렬되어있지 않은 두개의 값을 찾는 문제이다. 원소의 개수도 많지 않고, 찾아야 하는 원소도 두개뿐이니, 정렬한 다음에 같은 인덱스의 다른 원소 둘을 찾아 출력하면 된다. 코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;int n;vector diff;string symbol = "BSGPD";void input() { cin >> n; diff.resize..
문제https://www.acmicpc.net/problem/17609시간 제한메모리 제한solved.ac 티어1초(추가 시간 없음)512MB골드 5풀이 밀린 문제이다. 일반적인 회문은 원래 문자와 뒤집은 문자가 같은 것을 의미하지만, 해당 문제에서는 유사 회문이라는 개념을 제시한다. 유사회문이란 원래 회문은 아니지만 문자를 단 한개를 지웠을 때 회문이 되는 문자를 의미한다. 이 문제에서는 어떤 문자가 회문인지, 유사회문인지, 그것도 아닌지 모두 판단해보는 문제이다. 일반적인 회문 판단은 풀이할 필요가 없을 듯하니, 코드를 바로 읽어보면 될 것 같다. 우리가 중요하게 봐야하는건 유사회문 판별이다. 일반적인 회문처럼 문자열의 맨 앞과 맨 뒤를 검사하되, 중간에서 다른 문자를 만날수도 있을 것이다. 하지만..
문제 시간 제한메모리 제한solved.ac 티어2초256MB골드 4풀이이 문제도 밀린 문제이다. 언제 정리 다하나... 각설하고, 풀이를 해보겠다. 2467번이자 2470번 문제인 두 용액 문제(https://codejin.tistory.com/270)와 매우 유사한 문제이다. 해당 문제에서는 두 수의 합의 최솟값을 찾는 문제였지만, 이번 문제는 두 수의 합이 해당 배열에 존재하는지 여부를 따지는 문제이다. 유의할 점은 배열에 값이 같더라도 다른 값으로 본다는 점이다. 배열에 10이 두개 있고, 다른 두수의 합으로 10을 만들 수 있다면 이 두개 모두 좋은수이기 때문에 개수를 2개 올려줘야 한다. 입력받은 배열을 선형 탐색하면서, 원소 하나를 선택 한 후, 투포인터를 통해 해당 값을 만들 수 있는지 따져..
문제https://www.acmicpc.net/problem/12904시간 제한메모리 제한solved.ac 티어2초512MB골드 5풀이 밀린문제 풀이다. 이전번에 풀이한 12919번(https://codejin.tistory.com/282) 보다 덜 복잡한 문제이다. 저번 문제는 b를 추가한 후 문자열을 뒤집었기 때문에 문자열의 맨 앞과 맨 뒤를 고려해야하는 문제였지만. 이번 문제는 이보단 덜 복잡하다. 이 문제 역시 S->T로 가는 것은 경우의 수가 매우 많다. 문자열을 뒤집는 연산이 끼어있기 때문에, S에 적당히 연산을 한 S'가 T의 부분문자열이 아닐수도 있다. 부분문자열이더라도 여러 곳에서 등장할 수 있으며, 이때마다 어떤 연산을 고르는 것이 최적일지는 구분하기 힘들다. 하지만 T->S로 바꿔보..
문제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작업을 할 수도 있다. 당연히 모든 경우의 수..
