Social Developer

어제보다 한 걸음 더

Algorithms

바로 직전에 풀었던 수들의 합2(2003번) 문제와 매우 유사하다. sdesigner.tistory.com/58 투 포인터로 S보다 큰 경우를 찾고, 경우의 수 대신 범위의 길이를 출력해주면 되겠다. 이번 문제에서도 N이 100,000인 경우 모든 원소가 10000이라고 해도 합이 약 10억이다. int형 변수를 사용하는데 문제가 없고 0.5초 시간 제한에도 딱히 문제가 없다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, S; static int arr[]; static int ans; static int star..

2021. 2. 5.

Algorithms

전형적인 투 포인터 문제다. 수열 하나에 포인터 두 개를 두고 탐색해주면 된다. 수열의 길이인 N의 최댓값이 10,000인데, 각 원소가 30,000을 넘지 않으므로 수열의 모든 원소를 합쳤을 경우에도 int의 범위에 해당해 처리하는데 문제가 없다. 마침 합으로 만들어야 하는 M의 경우에도 최댓값이 3억으로 알맞게 주어졌다. 시간 제한은 0.5초로 다른 문제와 비교해 길지 않은 편인데, 투 포인터로 배열 하나를 모두 돌아다녀야 2N으로 O(N)이고 최악의 경우 길이 10,000이라고 해도 20,000 번 안에 탐색이 끝나니까 0.5초면 충분하겠다. 주 풀이는 합에 포함할 범위의 처음과 끝을 나타내는 포인터 2개(start, end), 합을 저장할 변수 1개(sum), 합이 M과 같을 경우의 수를 세는 변..

2021. 2. 5.

Algorithms

문제를 잘 이해해야겠다. 지문에서 크기가 양수인 부분수열 중에서~ 부분이 있는데 크기가 양수라는 말 그대로 이해하지 못하고, 값을 양수라고 생각했다. 지금 보면 헷갈릴 이유가 없는데, 처음 접했을 때는 이상하게 헷갈렸다. 크기가 양수인 부분수열이라 하면 아무 것도 선택하지 않는 상황만을 제외하면 되겠다. 그런 경우도 부분수열이라고 할 수 있는지는 몰랐지만 아마 집합에서의 부분집합에서 공집합 개념과 유사하지 않은가 싶다. 풀이는 먼저 DFS, 백트래킹 개념을 이용하면 된다. 수열의 각 원소로 구할 수 있는 값을 모두 구하면서, 값이 S와 동일한지 아닌지를 체크하면 되겠다. 시간 제한이 2초로 주어졌는데, 수열의 길이인 N의 최댓값이 20이다. 각 원소를 합에 포함할 지, 하지 않을지 두 가지 선택지를 모든..

2021. 2. 5.