등반

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2749, 11444 2749 문제 해설 재귀나 반복 문제를 풀다 보면 한 번쯤 만나는 피보나치의 수에 관한 문제다. 그런데 입력 값 n의 범위가 1~10^18사이의 정수다. 너무 크다. 그래서 1,000,000으로 나눈 나머지를 출력하라고 한다. 정해는 피사노 주기를 이용하는 것 같다. 본인은 일단 구해야 하는 피보나치의 수는 모두 구했다. 일단, 피보나치의 수를 살펴보자 Fn = Fn-1 + Fn-2 (n ≥ 2) 이렇게 생겼다. 단순 재귀를 이용한 풀이는 원하는 수를 구하..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 해설 부분 문자열은 한 문자열에서 연속한 부분을 떼어낸 문자열이다. 주어진 문자열 중 긴 문자열에 더미 문자열을 붙이고 완전탐색 시켰는데 통과했다... 얼떨떨했따... 긴 문자열의 비교 시작 부분을 이동시키며, 작은 문자열의 길이만큼 비교했다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; int ..

https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 문제 해설 1. 나3 : x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다. 2. 곱2 : x를 2로 곱한다. 어떤 수 x에 1, 2 두 가지 연산을 N번 시행했을 때, 수열 A가 나온다. 이 수열 A의 순서를 뒤섞은 수열 B로부터 A를 찾아내는 문제다. 살펴볼 것 1. 주어진 수열에 있는 원소는 중복이 있을까? 중복은 없다. 연산은 3으로 나누거나 2로 곱하는 것뿐이다. ..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 해설 포인트는 다음과 같다. C[i] = 지금까지 만든 길이가 i인 증가 부분 수열 중 최소 마지막 값 => C의 인덱스를 LIS의 길이와 연관시키고, 최소 마지막 값을 기록해 둠으로써 해당 값 보다 현재 비교할 수열의 값이 큰 경우 길이 i+1인 부분 수열을 만들 수 있다. 이때, C에 저장된 수는 오름차순으로 정렬된다. >> 정렬된 상태이므로 이분 탐색이 가능하다. #include #de..

https://www.acmicpc.net/problem/12034 12034번: 김인천씨의 식료품가게 (Large) 입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가 www.acmicpc.net 문제 해설 2N개의 가격표를 순회하며 정확히 75% 할인된 가격만 뽑아내 출력하는 문제다. 이 경우 map이나 set은 중복을 없애기 때문에 이용할 수 없다. multimap이나 multiset은 가능하다. 본인은 인덱스를 통한 접근이 유용할 것 같아서 vector로 해결했다. #include #define fio cin.tie(0)->sync_with_stdio(0..

https://www.acmicpc.net/problem/11645 11645번: I’ve Been Everywhere, Man The first line of input contains a single positive integer T ≤ 50 indicating the number of test cases. The first line of each test case also contains a single positive integer n indicating the number of work trips Alice has taken so far. The following n www.acmicpc.net 문제 해설 주인공이 다녀온 모든 도시의 개수를 출력하는 문제다.(중복 없이) 이런 문제는 map[st..

https://www.acmicpc.net/problem/11507 11507번: 카드셋트 예제1 : 12 12 11 13은 잃어버린 P카드 : 12개, K : 12개, H : 11개, T : 13라는 뜻이다. 예제2 : 같은 카드(H02)가 존재하므로 GRESKA을 출력하였다. www.acmicpc.net 문제 해설 잃어버린 카드의 목록이 주어질 때, 카드의 모양을 구분하여 갖고 있는 카드의 수를 출력하는 문제다. 구현 문제에 가깝다고 생각한다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include int main(){ fio; string S; cin >> S; set P, K, H, T; bool dupl ..

https://www.acmicpc.net/problem/11346 11346번: Cornell Party - Retry Ezra Cornell and A. D. White learned their lesson from their last party, so this time they decided to use names instead of identifiers. They also realized that they shouldn’t trust their memories so much, so they’ve decided to write down the guest name www.acmicpc.net 문제 해설 코넬에서 파티를 하는데, 두 명이 각각 참가자들의 명부를 기록한다. 동명이인은 없다. 몇 명이 있는..

https://www.acmicpc.net/problem/11235 11235번: Polling Output the name of the candidate with the most votes. If there is a tie, output out all of the names of candidates with the most votes, one per line, in alphabetical order. Do not output any spaces, and do not output blank lines between names. www.acmicpc.net 문제 해설 가장 많이 등장한 인물의 이름을 출력하는 문제다. 해당 인물이 유일하지 않은 경우, 사전 순으로 정렬해 모두 출력한다. 이런 문제는 map[..

https://www.acmicpc.net/problem/11116 11116번: 교통량 첫 번째 줄에 n (1 ≤ n ≤ 100) 까지의 테스트 케이스의 개수를 입력 한다. 각각의 테스트 케이스에는 박스에서 측정 된 시간 기록의 개수 m (m ≤ 200)을 입력한다. 다음 줄에는 왼쪽 박스에서 www.acmicpc.net 문제 해설 왼쪽 줄을 지나간 시간과 오른쪽 줄을 지나간 시간이 주어질 때, 왼쪽에서 오른쪽으로 지나간 교통량을 구하는 문제다. 왼쪽에서 오른쪽으로 지나간 교통량이 될 수 있는 경우는 왼쪽 줄에 t, t+500이, 오른쪽 줄에 t+1000, t+1500이 존재하는 t이다. map을 이용해 각각 log(n) 시간에 탐색해 해결할 수 있다. #include #define fio cin.ti..