문제https://www.acmicpc.net/problem/1036시간 제한메모리 제한solved.ac 티어2초128MB골드 2풀이 이 문제는 1339번을 풀어본 기억이 있어 쉽게 풀 수 있었다. 1339번 문제는 각 자릿수를 알파벳으로 바꾸고, n개의 숫자들을 더한 후, 알파벳에 숫자들을 매핑시켰을때의 최댓값을 구하는 문제이다. 자세한건, 문제 풀이한 글을 읽어보도록 하자. 백준 1339번 C++ 풀이https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있codejin.tistory.com 1339번 문제와 유사하게..
문제https://www.acmicpc.net/problem/1715시간 제한메모리 제한solved.ac 티어2초128MB골드 4풀이 15903번 문제와 거의 같은 문제이다. 당시 문제 풀이는 https://codejin.tistory.com/203 에서 확인할 수 있다. 백준 15903번 C++ 풀이https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄codejin.tistory.com 결국은 제일 작은값 끼리 더해나가면서 값이 증가하는 폭을 최대한 줄이면 최종적인 합도 최솟값이 된다. 그리디하..
문제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/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/16953시간 제한메모리 제한solved.ac 티어2초512MB실버 2 풀이1이 문제는 정말 생각할 수 있는 부분이 많은 좋은 문제라고 생각한다. 일단 문제를 보고 바로 든 생각은 그래프 문제구나 싶었다. 실제로 두 과정을 통해 a를 b로 만드는 최소 연산 횟수 + 1(a에서 b로 이동하는 최단경로)을 구하는 것이기 때문이다. a, b의 최댓값이 10^9로 약 2^30에 근접하고, 두 연산이 모두 곱하거나(2x), 곱하고 더하는 연산(10x + 1)이기 때문에 아무리 큰 케이스를 주더라도 연산은 30번에 근접할 것이다. 그리고, 나름의 최적화를 시도하여 큰 값부터 우선 처리하면, 더 빠르게 구할 수 있을거라고 생각하여 우선순위큐를 사용하여 bf..
