https://www.acmicpc.net/problem/18511 재귀함수를 활용하는 문제. 3^9 = 19683 으로 그렇게 큰 범위의 숫자가 아니기 때문에 K를 선택해서 수를 구성하는 모든 경우의 수를 직접 탐색해봐도 시간초과 없이 문제를 해결할 수 있다. 재귀함수를 사용하는게 일반적이고 깔끔한 풀이이다. 재귀함수를 사용한 탐색 도중에 N의 범위를 넘어가는 경우 음수(-1) 등을 반환하도록 처리해주면 된다. #include using namespace std; int N,M; vector K; int recur(int val){ if(val > N) return -1; int ans = val; for(auto k : K){ ans = max(ans, recur(val*10 + k)); } retu..
구현 문제. https://www.acmicpc.net/problem/1337 1337번: 올바른 배열 첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이 www.acmicpc.net O(5N) 등의 다양한 풀이가 있는듯 한데, 나는 O(N^2) 풀이를 구상했고 이걸로 구현해서 정답을 받았다. 일단 입력으로 주어진 배열을 정렬한 다음에, 두 인덱스 i와 j ( i < j ) 를 잡는다. 해당 인덱스에 있는 배열 값의 차는 v[i] - v[j] 이고, 해당 인덱스 구간에 있는 배열 값의 갯수는 i-j+1이다. 추가해야할 원소를 최소로 만들기 위해서 ..
https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 최대공약수를 이용하는 문제. 각 동생의 위치 $A_i$ 에 대해서 수빈이와의 거리 $dir_i$ 를 계산한다. $dir_i$ 거리를 이동하는 방법으로, 수빈이는 한번에 D만큼만 이동할 수 있기 때문에 $dir_i$ 의 약수가 D이면 수빈이가 동생을 찾을 수 있다. 가장 작은 약수는 1이므로 모든 경우에 수빈이는 동생을 찾을 수 있다. 각 $dir_i$의 약수들에 대..
https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 1차원 DP 문제였다. 피보나치 함수(이하 fibo) 의 호출횟수를 수동으로 살펴보도록 하겠다. fibo[0] = 1 fibo[1] = 1 fibo[2] = 3 fibo[3] = 5 fibo[4] = 9 .... 규칙을 파악할 수 있는가? fibo[k] = (1+fibo[k-1]+fibo[k-2]) 이다. 1은 자기자신 역시 호출되었기에 더해줘야 하는 수고 fibo[k-1]과 fibo[k-2] 는..
https://www.acmicpc.net/problem/14582 14582번: 오늘도 졌다 첫 번째 줄에는 9개의 정수가 주어지는데, 오늘 경기에서 울림 제미니스가 1회 초, 2회 초, ..., 9회 초에 낸 득점이 주어진다. 두 번째 줄에도 9개의 정수가 주어지는데, 스타트링크 걸리버스가 1회 www.acmicpc.net 문제에서 요구하는대로 구현하면 되는 문제. 제미니스가 이기고 있던 적이 있는지를 체크하는 플래그 변수 flag1, flag1이 켜져있는(이긴적이 있는) 상황에서 스타트링크가 이기고 있다면 flag2를 켜줬다. flag2가 켜져있는지 꺼져있는지의 여부가 정답이 된다. 각 회 초가 끝난 바로 뒤 flag1을 갱신해줘야 함에 유의해야한다. #include using namespace s..
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 고민을 오래 해봐야 하는 문제 수의 범위가 크다. 일단 수의 범위가 매우 큰 편이라서, 전처리를 통해서 시간을 아낄 생각을 해봐야 한다. 대부분의 변수에서 long long 형이 필요하니까, 그냥 모든 변수 자료형을 ll으로 통일하면 깔끔해진다. cnt[k] 를 비트 k개 범위(0~2^k-1) 의 수들에서 등장하는 2진수 1의 개수의 합 으로 정의한다. 숫자 K가 i개의 ..