LAZY_lazy_LaZy

https://www.acmicpc.net/problem/1300

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력 

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

시행착오

문제를 처음 읽으면 '배열을 만들었다' 라는 말에 현혹되어 자칫하면 배열을 만들 수 있는데 배열을 만들지 않고도 풀 수 있는 문제이다.

첫 접근은 이진 탐색을 사용하지 못했다.

대체 이걸 어떻게 이진탐색으로 접근할 지 감이 잡히지 않아 중첩 for문을 만들어 i = j 일 때는 count값에 1을 더해주고 아닐 때는 2를 더해주는 방식을 사용하였다.

N*N 개의 요소에 모두 접근하지는 않고 j = i 일 때부터 검사했다.

이 방식을 사용하면 답은 나오지만 입력 범위 때문에 시간 초과가 뜬다.

이렇게 하면 안된다....

검색을 통해 이곳 저곳을 기웃거리며 이진탐색을 이용해 풀어보았다. 

<풀이과정>

1. K 번째 숫자를 찾기 위해서 이분탐색 범위의 최솟값을 1, 최댓값을 K로 둔다. (중복되는 숫자들로 인해 K번째 숫자는 절대 K보다 클 수 없으므로)

2. 설정한 범위의 중간 값 mid를 구한다.

3. N번 반복문을 돌려 각 행에 mid 이하의 수가 몇개 있는 지 개수를 센다. 

   이 때, i*j <= mid를 만족해야하므로 개수 j는 mid/i 의 값을 가지게 된다. 

   한 번 반복 할 때마다 mid / i 값을 cnt에 더해 주는 데, 이 때 더하는 값이 N값보다 커지면 안되므로 mid / i와 N 중       작은 값을 cnt에 더해주기로 한다. 

4. 반복문이 끝나면 cnt와 K값을 비교하여 왼쪽 범위를 검사할 지, 오른 쪽 범위를 검사할 지 판단한다.

   (cnt > K 일 땐 왼쪽, cnt  < K 일 땐 오른쪽)

* 이 때 cnt가 K와 같을 때 바로 mid를 리턴하지 않고 다시 왼쪽 범위를 검사하는데, 이는 mid가 i*j 숫자 중 없을 때를 고려한 시행이다. 

예를 들어 

    1 2 3 

    2 4 6 

    3 6 9   

이러한 배열이 들어오고 K = 8일 때,

실제 답은 6이지만 mid 가 7일 때에도 cnt = K 가 가능하다. 그렇다고 해서 7을 리턴할 수는 없으므로 cnt  = K인 가장 작은 숫자를 찾기 위해 다시 한 번 왼쪽 범위를 탐색하는 것이다. 

5. (범위의 최솟값) > (범위의 최댓값)을 만족할 때 범위의 최솟값을 답으로 리턴한다. (mid = start 였을 때) 

#include <iostream>
#include <algorithm>
typedef long long ll;

using namespace std;

ll N = 0;
ll K = 0;
ll mid = 0;

ll BinarySearch(ll start, ll end) {


	if (start > end) {
		return start;
	}

	mid = (start + end) / 2;

	ll cnt = 0;


	for (ll i = 1; i <= N; i++) {
		cnt += min(mid / i, N);
	}


	if (cnt >= K) {
		return BinarySearch(start, mid - 1);
	}
	else {
		return BinarySearch(mid + 1, end);
	}
}


int main()
{
	cin >> N;
	cin >> K;

	cout << BinarySearch(1, K);

}

<결과>

이상한 부분 있으면 말해주세요! 

https://www.acmicpc.net/problem/1182

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

https://terms.naver.com/entry.nhn?docId=5668858&cid=60207&categoryId=60207

부분수열이 무엇인 지 알아야 풀 수 있는 문제이다. 

수열에서 항의 일부를 골라 순서대로 나열한 수열을 부분 수열이라고 한다.

이 때 고르는 수열은 일정한 법칙 없이 뽑아도 된다. 순서만 맞으면...

<풀이 과정>

1. 각각의 수를 더하고 지나갈 때와 더하지 않고 지나갈 때를 고려하여 부분수열의 모든 경우의 수를 체크한다.

(-> 이부분은 재귀호출로 해결한다.) 

2. 매 호출 마다 부분수열의 합이 S인지, 마지막 인덱스까지 확인했는지 검사한다. 

3. S 값이 0일 때를 고려하여 모든 값을 더하지 않고 뛰어넘은 경우를 제거해준다. 

어려워서 여기저기 찾아보며 했는데, 처음 이해하기까지가 힘들었다.  

#include <iostream>
#include <vector>

using namespace std;

int answer = 0;
int N, S;
int arr[10000] = { 0 };

void sumSubseq(int i, int sum) {
	// 부분수열의 합이 S이고 마지막까지 확인을 했을 때 answer += 1  
	if (sum == S && i == N) {
		answer += 1;
		return;
	}

	// 부분수열의 합이 S가 아니지만 마지막까지 확인을 했을 때 return
	if (i == N)
		return;


	// 현재 확인한 값을 더할 때
	sumSubseq(i + 1, sum + arr[i]);

	// 현재 확인한 값을 더하지 않을 때 
	sumSubseq(i + 1, sum);
}

int main()
{

	cin >> N >> S;

	for (int i = 0; i < N; i++)
		cin >> arr[i];


	sumSubseq(0, 0);

	// S가 0일 때 모든 값을 더하지 않고 뛰어넘은 경우를 제거
	if (S == 0)
		answer--;


	cout << answer << endl;
}

<결과>