Do you believe in you?

[문제]https://www.acmicpc.net/problem/1463정수 x 가 주어졌을 때, x 를 1로 만드는 최소 연산의 수를 찾는 문제이다. x 를 1로 만드는 연산은 3가지가 있다. 1) x 가 3 으로 나누어 떨어지면 x 를 3 으로 나눈다.2) x 가 2 로 나누어 떨어지면 x 를 2 로 나눈다.3) 1)2) 가 아니면 x 에서 1을 뺀다. 정수 x 값의 범위는 1 ≤ x ≤ 10^6 이다.제한시간은 0.15초 이다. [풀이]정수 x 의 최대값이 10^6 이기 때문에 O(n^2) 만 되어도 문제의 제한시간을 넘긴다. 즉, 완전탐색으로 풀면 안된다. 점화식을 찾아야 한다.'D[x] = x를 1로 만드는 최소 연산의 수' 라고 두고 D[1] 부터 구해보자. D[1] = 1D[2] = D[2/..

문제 & 설명https://www.acmicpc.net/problem/1269  풀이A의 원소 하나하나의 값을 B에서 찾을 때 이분탐색을 진행한다.  정답 코드#include #include #include using namespace std;int main() { int aNum, bNum, input, sum = 0; int l, h, mid; // 이분탐색을 위한 변수 vector As, Bs; // Input cin >> aNum >> bNum; for (int i = 0; i > input; As.push_back(input); } for (int i = 0; i > input; Bs.push_back(input); } ..

[문제]https://www.acmicpc.net/problem/2343 N 개의 강의가 주어질 때 강의들을 몇개씩 엮어서 블루레이로 만들어서 판매하려고 한다.강의들을 엮을 때 강의의 순서가 바뀌면안되고, 블루레이의 크기는 모두 같아야 한다.즉, 강의를 쪼갤 수 있는 최소합을 찾자. *문제조건강의의 수  N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)각 강의의 길이는 10,000분을 넘지 않는다. [예시]9 31 2 3 4 5 6 7 8 917 강의는 총 9개이고, 블루레이는 총 3개 가지고 있다. 1번 블루레이에 1, 2, 3, 4, 52번 블루레이에 6, 73번 블루레이에 8, 9 을 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에 블..

https://www.acmicpc.net/problem/2792 아이들의 수와 보석 색상의 수, 보석의 개수가 주어진다.모든 보석을 나누어줄 때 최대한 차이가 나지 않게 나누어주는 방법을 구하는 문제이다. 한 아이가 갖는 보석의 수를 질투심이라 표현했다.이 때 한 아이는 같은 보석의 색상만 가져야 한다. 또한, 보석을 못받는 아이는 있어도 남는 보석은 없어야 한다. [입력]첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.[출력]첫째 줄에 질투심의 최솟값을 출력한다.  [풀이]하나의 보석의 수가 ..

폭발, 짝짓기 문제는 stack을 떠올리자. [문제]https://www.acmicpc.net/problem/9935 문자열에 폭발 문자열이 있다.폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보자. 남아있는 문자가 없는 경우 "FRULA"를 출력하자. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.폭발 문자열의 길이는 1보다 크거나 같고, 36보다 작거나 같다.두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다. [풀이]문자열의 길이가 매우 기므로, 완전탐색으로는 풀 수 없다.문자열 비교를 위해 stack 자료구조나 erase 함수를 이용하여 for문 하나..

구간이 나오면 정렬!을 떠올리자. 어느정도의 복잡도를 감소시킬 수 있다. [문제]https://www.acmicpc.net/problem/1931 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있을 때,각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾자. 회의의 수 N(1 ≤ N ≤ 100,000)시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0 [해결방법]회의의 수가 최대 100,000 개 이므로 완전탐색으로는 풀 수 없다. Greedy 로 풀어야 한다.특히, 구간이 주어지면 정렬을 생각하자. 라인스위핑 문제라 부른다. 1) 시작 시간을 기준으로 정렬2) 끝나는 시간을 기준으로 정렬3) 회의 시간을 기준으로 정렬 위 3가지 처럼 모든 풀이방법을 생각하..

[문제]https://www.acmicpc.net/problem/2109 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불한다.첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.가장 많은 돈을 벌 수 있는 순회강연을 찾고 그 돈을 출력하라.  [풀이]d 일 안에 와서 강연이라는 조건을 d 일에 강연하는 걸로 잘못 이해하여 map 으로 풀다가 틀렸다.게시판을 참고해보니 d 일 안에 와서 라는 조건이 있기에 d 일 안이면 언제든 강연할 수 있다는 것을 생각해야 한다. n개의 대학의 전부를 비교하기에는 시간제한이 되므로 sort, priority queue 를 이용한 Greedy  로 접근해야 한다.기한..

[문제] 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어진다. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어온다. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어온다. 최종적으로 입력으로 숫자가 들어왔다면 그 숫자에 해당하..

문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램 조건 N은 2 이상 100,000 이하 주어지는 수들은 모두 -100 이상 100 이하 예제 문제/답 10 2 3 -2 -4 -9 0 3 7 13 8 -3 10개의 수가 주어지고, 2일치를 연속적으로 더했을 때 갖 값, => 정답은 21 해결방법 첨에 규칙 찾아서 하..

[문제] https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 파일의 개수와 패턴이 주어진다. 패턴은 a*b 이런 식으로 주어지되, *엔 공란을 포함한 여러 상이한 문자열이 포함될 수 있다. 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE" 를 출력한다. 주의할 점은, a*b 이런 식으로 패턴은 1문자가 아니라 ab*bc 이런 식으로 2글자, 3글자... 가 올 수 있다는 것. 예제 입력 3 a*d a..