길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. 1. A의 앞에 아무 알파벳이나 추가한다. 2. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.
[입력] 첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.
[출력] A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.
✅ 문제 풀이
문자열을 다루는 문제이다.
문제를 가만 보면, A의 앞에 문자를 추가하거나 뒤에 문자를 추가하거나에 초점을 맞출 시에는 복잡해진다.
어차피 채울 수 있는 문자열은 B와 동일한 문자열을 채우면 되기 때문에, 상관하지 않도록 한다.
A문자열 그 자체만을 보고, B문자열과 비교하는 것이다.
B문자열의 앞에서부터 A문자열 크키만큼 비교하는데, 그 차이가 가장 적을 때가 A와 B의 차이를 최소로 하는 것이다.
예를 들어서 B에 A문자열이 완전히 포함된다면 어떨까?
그럼 A문자열이 포함되는 부분을 제외하고만 A에 앞 뒤로 B와 동일하게 문자를 붙혀준다면, 두 문자열은 동일한게 되는 것이므로 차이는 0이 된다.
따라서 A가 B 중에서 가장 적게 차이나는 값을 구하면 된다.
그러기 위해 B에서 A를 뺀 값+1 만큼 for문을 돌면서 A와 B를 비교하는데, 이때 B를 그냥 비교하는게 아니라, A의 길이만큼 일정부분 잘라서 비교하도록 하였다. 이때는 string의 substr함수를 사용하였다.
이런식으로 A를 B의 앞 부터 밀어가면서 비교해보는 것이다.
☑ 코드 전문
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string a, b;
cin >> a >> b;
int cnt = 50;
for (int i = 0; i < b.length() - a.length() + 1; i++) {
string str = b.substr(i, a.length());
int now = 0;
for (int j = 0; j < a.length(); j++) {
if (a[j] != str[j]) now++;
}
cnt = min(cnt, now);
}
cout << cnt;
}
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 1100000000 0100000000 0000100000 0000100000 0011000111 0000100111
[입력] 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
[출력] 필요한 배추흰지렁이의 개수를 구하라.
✅ 문제 풀이
값이 1이면서 동서남북으로 인접한 1이 존재할 때 한 영역이 되기 때문에, 한 영역안에서는 모든 1이 서로 인접한 1이 존재한다는 것이다. 따라서 어떤 값이 1이면 연쇄적으로 인접한 값을 마주할 때 까지 탐색하여 하나의 영역으로 구할 수 있다. 따라서 이 문제는 DFS로 해결할 수 있다.
먼저 매 테스트 케이스마다 배열에 값을 저장한다. 입력으로 받는 k개의 배추 위치에 대해 1로 저장하고 나머지는 0으로 저장하면 된다.
배열의 크기만큼 순회하는데, 값이 1이면 첫번 째 영역에 대한 시작이므로, count를 1 증가시킨 후, dfs 함수를 호출한다.
dfs 함수에서는 현재 값이 1인 위치와, arr를 &로 넘겨준다. &로 넘겨주는 이유는 방문한 칸에 대해서는 arr의 값을 수정해주기 위해서이다.
dfs 함수가 호출되면, 현재 인자로 받은 위치의 값을 0으로 바꾸어준다. 그 이유는 방문했음을 나타내기 위함과, 나중에 main의 for문에서 재방문 하지 않게 하기 위함이다.=> 이 문제의 핵심이다.
그리고 현재의 위치를 기준으로 동서남북 방향에 있는 값이 1인지 확인한다.
1이라면 같은 영역이므로, 그 칸을 기준으로 dfs 함수를 호출하도록 한다.
따라서 위의 과정을 반복하다 보면 동일한 영역에 해당하는 값들이 1에서 모두 0으로 바뀌게 되고, main문에서 해당 영역에 해대 시작했던 탐색이 끝나게 되어 하나의 영역을 탐색할 수 있게 되는 것이다.
위 과정을 거친 후 최종 count 값이 바로 영역의 개수가 되고, 필요한 지렁이의 개수가 된다.
☑ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void dfs(int x, int y, vector<vector<int>> &arr) {
arr[x][y] = 0;
for (int n = 0; n < 4; n++) {
int r = x + dx[n];
int c = y + dy[n];
if (r>=0&&r<arr.size()&&c>=0&&c<arr[0].size()&&arr[r][c] == 1) {
dfs(r, c, arr);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;//테스트 케이스 개수
cin >> T;
for (int i = 0; i < T; i++) {
int M, N, K;//가로, 세로, 총 배추 개수
cin >> M >> N >> K;
vector<vector<int>> arr(N, vector<int>(M, 0));//배추밭
for (int j = 0; j < K; j++) {
int x, y;
cin >> y >> x;
arr[x][y] = 1;
}//배추 심기
int count = 0;//배추흰지렁이의 개수
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
if (arr[j][k] == 1) {
count++;
dfs(j, k, arr);
}
}
}
cout << count << "\n";
}
}
서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다. 따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다. 프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.
[입력] 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.
[출력] 건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다.
문제를 요약하자면..
1번부터 N번까지의 N개의 건물이 있을 때, 주어진 건설 순서 (1 2 = 1->2) 에 따라서 각 건물이 건설될 수 있다.
예를 들어 앞의 그림에 따르면, 2와 3은 1이 건설된 후에야 건설할수 있고, 4는 2와 3이 모두 건설된 후에야 건설할 수 있다.
각 건물을 건설하는데에는 DN의 시간이 소요되고, 입력으로 주어진다.
이때 입력으로 받는 건물 W를 건설하는데 소요되는 최소시간을 구하는 문제이다.
✅ 문제 풀이
W를 건설하기 위해서는 W하위에 연결된 모든 건물이 완료되어야 하기 때문에, W까지 연결되는 여러 경로 중 에서 소요되는 시간이 최대일 때와 같다.
=> 왜 최대이냐?
W가 건설되기 전까지는, W를 건설하기 위해 먼저 건설되어야 하는 건물들 모두가 건설을 마쳐야 W를 건설할 수 있기 때문에, 위의 예시처럼 건물 2가 1초 밖에 걸리지 않다 하더라도, 건물4가 건설되려면 건물3도 건설되어야 하므로, 둘 중 더 소요시간이 긴 건물 3에 의해 100초가 더해져야 한다. 따라서 총 10초(건물1)+100초(건물2,3)+10초(건물4)=120초가 소요된다.
따라서 이 문제는 위상정렬을 이용해서 해결할 수 있다.
다음 사항들을 고려해야 한다.
1. 각 건물(노드)을 건설한 바로 다음에 건설될 수 있는 건물들을 저장해야 한다. => vector<int> node[1005]를 vector 타입의 배열을 만들어서, 각 노드(인덱스=건물번호)에 이전 건물에 대한 정보를 vector로 추가해준다.
2. 각 건물까지 짓는데 걸리는 최소 시간을 저장하는 배열이 있어야 한다.
=> vector<int> sum(1005,0); => 각 노드(인덱스=건물번호)에 저장한다.
3. 각 건물에 대한 깊이를 저장하는 배열이 있어야 한다. => 예시에서 보면 1은 선행 노드가 없으므로 깊이가 0, 2와 3은 선행노드가 1이 있으므로 1, 4는 선행노드가 1, 2-3이 있으므로 2이다.
=> vector<int> degree(1005,0)
이제 코드를 하나씩 만들어가 보자.
테스트 케이스 T를 받아 저장한다.
T번의 테스트 케이스를 진행하도록 for문을 작성하고, for문 안에서 아래 내용들이 동작하도록 구현한다.
건물을 개수를 입력받아 N에 저장한다.
건설 규칙의 개수를 입력받아 K에 저장한다.
다음을 미리 선언해준다. ✔ vector<int> D(1005,0) : 각 건물의 건설시간을 담은 크기가 1005인 벡터 D ✔ vector<int> sum(1005,0) : 각 건물을 완성하기까지 걸리는 시간을 담은 크기가 1005인 벡터 sum ✔ vector<int> node[1005] : 각 건물의 후행 건물을 담은 벡터 타입의 크기가 1005인 배열 node ✔ vector<int> degree(1005,0) : 각 건물(노드)의 깊이를 담은 크기가 1005인 벡터 degree =>값은 모두 0으로 초기화
각 건물의 건설시간을 건물 번호에 맞게 차례로 입력받는다. => 벡터 D의 1번 인덱스부터 1번 건물의 건설 시간을 입력받아 저장한다. => 그리고 sum의 동일한 인덱스에 입력받은 각각의 건설 시간을 저장해준다. sum에는 일단 각 건물에 대한 건설시간이 저장되어 있는 것이다. = 만약 맨 아래 노드라면 해당 건물을 짓는데는 해당 건물의 건설시간만 소요될 것이므로 미리 값을 지정해준다.
K개의 건설 규칙을 입력받자. for문을 연다.
건설 규칙을 입력받기 위해 선행 건물을 저장하는 x와, 후행 건물을 저장하는 y를 선언하고, 입력받아 저장한다.
node[x]에다가 y를 넣어준다. 현재 이 배열은 벡터 타입이므로 push_back하여 y를 저장한다.
그리고 y 이전에 x가 먼저 건설되기 때문에, y는 선행 노드가 있다는 것이므로, degree[y]를 1 늘려줘서 깊이를 1 높인다.
이렇게 K개의 규칙에 대해 다 실행한 후 for문이 끝나면 경로를 하나씩 접근해가며 sum을 갱신할 수 있다.
그 전에 W를 입력받아서 저장해둔다.모든 건물의 sum을 구한 후 그중 sum[W]를 통해 W건물까지 짓는데 걸리는 최소시간을 구할 수 있다. 다음을 진행하여 sum을 설정하자.
queue<int> q를 하나 생성하여 방문할 노드들을 저장하는 용도로 사용하자.
일단 모든 건물(=노드)를 for문을 통해 돌아보면서, 현재 노드의 degree가 0인지 확인한다.
현재 노드의 degree가 0이라면, 선행 노드가 없다는 것이므로, q에 현재 노드를 push한다.
for문을 다 돌면, while문을 통해 q가 빌 때 까지 다음을 수행한다.
q의 맨 앞에 있는 노드를 꺼내 top에 저장한다. 그리고 node[top]에 저장된 모든 후행 노드를 순회하면서 next에 저장한다.
만약 sum[top]+D[next] 가 sum[next]보다 크다면 sum[next]를 전자로 갱신시켜준다. =>이게 바로 같은 레벨에서는 최대로 걸리는 값으로 갱신해야 한다는 의미이다. 같은 레벨에 있는 건물은 다음 건물 짓기 전에 모두 건설완료되어야 하기 때문에 가장 오래 걸리는 건설 시간을 반영한다는 뜻이다.
그리고 degree[next]를 1 줄여서 선행 노드를 이미 방문했음을 표시한다.
그리고 degree[next]가 0이면 이 노드를 시작으로 위 과정을 반복하기 위해 q에 push한다.
그럼 while문을 충족하므로 과정을 반복한다.
맨 마지막 노드에서 degree[next]를 1 줄임으로써 0이 되면서 while문이 종료되고, 각 노드에 대한 최종 sum이 설정되었을 것이다.
그럼 이때 sum[W]를 출력하여 프로그램을 마친다.
☑ 코드 전문
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N, K, W, top, next;
vector<int> D(1005, 0);//각 건물의 건설시간
vector<int> node[1005];//노드 별 이어지는 노드
vector<int> degree(1005, 0);//루트로부터 몇번째에 있는지
vector<int> sum(1005, 0);//현재 노드까지의 총 건설 시간
queue<int> q;
cin >> N >> K;
for (int j = 1; j <= N; j++) {
cin >> D[j];
sum[j] = D[j];
}
for (int j = 0; j < K; j++) {
int x, y;
cin >> x >> y;
node[x].push_back(y);
degree[y]++;
}
cin >> W;
for (int j = 1; j <= N; j++) {
if (!degree[j]) {//내 아래로 없으면
q.push(j);//이 노드의 후행 노드들을 살펴보자
}
}
while (!q.empty()) {
top = q.front();
q.pop();
for (int j = 0; j < node[top].size(); j++) {
next = node[top][j];
if (sum[top] + D[next] > sum[next]) sum[next] = sum[top] + D[next];
degree[next]--;
if (!degree[next]) q.push(next);
}
}
cout << sum[W]<<"\n";
}
return 0;
}
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
첫째 줄에 S의 최솟값을 출력한다.
✅ 문제 풀이
크기가 각각 N인 A와 B배열을 입력받은 뒤, B는 그대로 두고, A만 재정렬 하여 A와 B의 원소를 각각 곱해서 최소의 값이 되도록 하는것이다.
여기서 구하고자 하는 것은 그때의 최소값이다.
따라서 A와 B가 어떻게 정렬이 되어 있던 간에, 결국 최소 값을 구하기 위해서는 한쪽은 가장 큰 값, 다른 한쪽은 가장 작은 값을 곱한 것이 최소가 된다.
따라서 A를 오름차순 정렬하고, B를 내림차순 정렬한 후에 각각의 원소끼리 차례로 곱한 값들을 더해주면 최소값이 나오게 된다.
B는 그대로 두되, A를 "재정렬" 하라는 말에 너무 초점을 맞추게 되면, 생각이 많아질 수 있으나, 목적인 최소값을 생각하면 쉽게 해결하는 문제이다.
☑ 코드 전문
#include<iostream>
#include<algorithm>
using namespace std;
bool compare(int a, int b) {
return a > b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int *A = new int[N];
int *B = new int[N];
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
cin >> B[i];
}
sort(A, A + N);//오름차순
sort(B, B + N, compare);//내림차순
int answer = 0;
for (int i = 0; i < N; i++) {
answer += A[i] * B[i];
}
cout << answer;
return 0;
}
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
입력 3 2 2 1 5 13 29
출력 1 5 67863915
✅ 문제 풀이
주어진 조건을 보면, n개의 사이트가 항상 일정한 순서대로 m개의 사이트와 연결되어야 하기 때문에, 순서를 고려하지 않는 경우의 수만 구하면 된다.
따라서 m개의 사이트 중 n개를 고르는 조합 문제이다.
mCn을 코드로만 구현하면 된다.
mCn의 수식을 보면 m에서 하나씩 줄여가면서 n개의 수를 곱하고, 1부터 n까지를 곱한 값을 나누어 주면 총 경우의 수와 같다.
☑ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n, m;
cin >> n >> m;
long answer = 1;
int k = 1;
for (int j = m; j > m - n; j--) {
answer *= j;
answer /= k;
k++;
}
cout << answer << "\n";
}
return 0;
}
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
입력예시 10 15 5 1 3 5 10 7 4 9 2 8
출력예시 2
✅ 문제 풀이
부분합이라고 해서 무조건 크기가 N인 배열에 누적합을 구해 놓으면 해결될 문제가 아니다.
이 문제에서 핵심은 "한번만" 순회하여 해결해야 한다는 것이다.
처음에는 for문 안에 부분 while문을 넣어서 결론적으로는 o(n^2)의 시간복잡도로 구현하였다. 결과는 역시 시간초과였다.
부분합 문제는 특히 o(n)으로 해결해야 한다.
그럼 어떻게 해결할 수 있을까?
문제를 풀면서 인지하고 있었던 것은, 앞에서부터 누적해 나가되, 그 값이 S이상이 되면 멈추는 것이다. 그리고 다시 앞에서부터 하나씩 줄여갔을 때에도 여전히 S이상이라면 이전 보다는 더 짧은 길이가 될 수 있다는 점이다.
그러면 여기서 알 수 있는 점은, 시작 점과 끝점을 가리키는 두개의 포인터가 필요하다는 것이다.
우리는 그것을 st, en이라고 할 것이다. 그리고 그 값은 각각 1부터 시작한다.
그리고 부분합을 가리키는 total을 선언하고, st와 en이 현재 1을 가리키므로, total은 수열의 1번째 값을 갖도록 한다.
answer는 최소 길이인데, 현재 수열의 최대 값은 100000이기 때문에, 초기값을 100001로 설정하여 min값을 찾아가도록 한다.
이제 while문을 통해 수열을 순회하는데, 시작점인 st는 끝점인 en보다는 작거나 같아야 하며, en이 N과 같아질 때까지 순회하도록 한다.
그리고 아래의 조건에 따라 수행한다.
만약 현재 total이 S보다 크다면, 조건을 만족한 것이므로, 현재의 answer값 (st-en+1)=현재 total을 이루는 길이를 비교해서 더 작은 값으로 answer를 갱신한다.
만약 total이 S보다 작다면, en을 하나 늘려서 다음 값을 total에 누적해주고, total이 S보다 크다면, total에서 st가 가리키는 값을 빼준 후 st를 하나 줄여준다.
=> 이렇게 되면, st를 줄였을 경우에도 total이 S조건보다 커서 answer가 더 작은 값으로 갱신될 수 있기 때문에, 이런식으로 한번의 순회로 답을 찾아갈 수 있는 것이다.
순회가 끝나고 난뒤에는, answer가 초기값 100001이 아니라면 한번이라도 S보다 큰 부분합이 있었다는 것이므로 answer를 출력하고, answer가 초기값 그대로였다면, S보다 큰 부분합이 없었다는 것이므로 0을 출력하도록 한다.
전체코드는 아래와 같다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, S;
cin >> N >> S;
vector<int> vec(100001, 0);
for (int i = 1; i <= N; i++) {
cin >> vec[i];
}
int answer = 100001;
int total = vec[1];//첫번째 값부터 담아서 시작
int st = 1;//시작 포인터
int en = 1;//끝 포인터
while (st <= en && en <= N) {
if (total >= S) answer = min(answer, en - st + 1);
if (total < S) {
en++;
total += vec[en];
}
else {
total -= vec[st];
st++;
}
}
if(answer!=100001) cout << answer;
else cout << 0;
return 0;
}
