`배열 기록`은 계속 유지해야하는 정보를 배열에 저장하는 유형을 의미한다.
배열 기록 유형 - 2
1. 시간에 따른 위치 - 매 초마다 위치를 배열에 저장. 인덱스 : 시간, 값 : 위치
2. 남은 횟수 배열로 기록하기
개념 : 시간에 따른 위치
A, B가 1초에 1m씩 움직입니다.
A는 9초 동안 앞으로 움직이다가, 3초간 뒤로 오고, 다시 5초간 앞으로 움직입니다.
B는 2초간 뒤로 갔다가, 앞으로 2초 갔다가, 1초간 뒤로 오고, 다시 12초간 앞으로 움직입니다.
A, B가 움직임을 시작한 이후에 다시 만나게 되는 시간은 몇 초 뒤일까요?
A,B의 시간에 따른 동선을 일직선 상에 표시하면 다음과 같습니다.
이때 A, B가 몇 초후에 최초로 만나는지를 구하고자 합니다.
주의할 점은 A, B가 위치상 같을 때만 조건이 아니라 시간과 위치가 동시에 같을 때여야 합니다. 다른 시점에 같은 위치를 방문한 겻은 최초로 만난 시간이 아니기 때문입니다.
방법 -2
1. 1초씩 시뮬레이션하면서 A, B의 위치를 동시에 확인
- 이게 왜 복잡한 방법인가? : 매초마다 A와 B의 이동 기록을 추적해야함.
2. A의 시간에 따른 이동을 배열에 저장하고, B의 시간에 따른 이동 기록을 배열에 저장
배열의 인덱스가 시간(초)이고, 그 안에 저장되는 값이 위치입니다.`a[시간] = 위치`
위의 도식에서는 일직선의 축이 위치가 마치 배열의 인덱스처럼 나타납니다. 위치를 인덱스로 잡지 않는 이유는 A, B가 오른쪽, 왼쪽 양방향으로 이동하면서 위치는 중복이 될 수 있기 때문입니다. 시간은 계속 증가하기 때문에 인덱스가 겹치지 않아 a[시간] = 위치가 됩니다.
A의 시간에 따른 위치를 기록하고 B의 시간에 따른 위치를 기록한 뒤, 0 초 부터 1초씩 증가시키면서 값이 최초로 같을 때 배열의 인덱스가 최초 만나는 시각이 됩니다.
Warm up : 만나는 그 순간
내 풀이
접근방법
- A와 B 각각 시간의 흐름에 따른 이동 위치를 1차원 배열에 저장한다. a[시간] =위치
- 현재 시간, 현재 위치를 저장하는 변수를 각각 두고, A, B가 t초만큼 d방향으로 이동할 때 시간을 누적하여 총 이동 시간을 구한다.
- A, B의 총 이동 시간 중 최소 시간으로 두 사람의 이동 기록 배열을 탐색한다.
e.g A는 총 10초간 이동, B는 2초간 이동했다면 2초까지만 동일 시각에 동일 위치에 있는지 확인한다. 3초 부터는 B가 이동하지 않았으므로 절대 A와 만날 수 없기 때문이다.
놓친 지점
- 최대 이동시간은 1,000이 아니라 1,000,000초이다.
- 조건의 범위가 1 <= t <= 1000, 1 <= n, m <= 1000이므로 최대 1000번 동안 각각 1000초를 이동한 것이 최댓값이 된다. 1000번 * 1000 초 = 1000초 인 것이다.
- A, B의 시간의 흐름에 따른 이동 위치를 기록한 배열의 크기가 1000이되면 런타임에러가 난다. `arr_a[1000]` 에서 `arr_a[1'000'004]`로 수정해야한다.
#include<bits/stdc++.h>
using namespace std;
int arr_a[1'000'004];
int arr_b[1'000'004];
int cur_time, cur_pos, n, m, t, t_a, t_b;
char d;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
// A의 시간에 따른 위치를 기록한다.
while(n--) {
cin >> d >> t ;
// cout << "d = " << d << " , t = " << t << "\n";
t_a += t;
while(t--) {
cur_time++;
if(d == 'R'){
arr_a[cur_time] = ++cur_pos;
}
else arr_a[cur_time] = --cur_pos;
}
}
cur_time = 0, cur_pos = 0;
while(m--) {
cin >> d >> t ;
t_b += t;
while(t--) {
cur_time++;
if(d == 'R'){
arr_b[cur_time] = ++cur_pos;
}
else arr_b[cur_time] = --cur_pos;
}
}
bool state = false;
// 둘의 이동 시간 중 작은 시간 만큼 탐색을 한다.
t = min(t_a, t_b);
for(int i = 1; i <= t; i++) { // i = 0일 때는 아직 움직이지 않았기 때문에 1부터 시작
if(arr_a[i] == arr_b[i]) {
cout << i << "\n"; state = true; break;
}
}
if(!state) cout << -1 << "\n"; // 둘다 만나지 않는 경우 예외처리
return 0;
}
개념 : 남은 횟수를 배열로 기록하기
3명의 사람 A, B, C가 각각 숫자 5, 10, 8을 생각하고 있습니다.
각 사람은 처음 3개의 사탕을 가지고 있고, 5번의 질문에 대해 조건을 만족할 때마다 사탕을 하나씩 잃게 됩니다.
가장 빨리 사탕이 사라지게 되는 사람은 누구일까요?
5개의 질문 목록은 다음과 같습니다.
1. 숫자가 3 이상인 경우
2. 숫자가 5 이하인 경우
3. 숫자가 7 이상인 경우
4. 숫자가 2 이상 8 이하인 경우
5. 숫자가 10 미만인 경우
Warmup : 벌금은 누구에게
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-who-will-pay/description
벌금은 누구에게 설명 | 코드트리
벌금은 누구에게을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
접근 방법
- 매 시행 (벌칙에 걸린 학생의 번호를 확인)마다 학생들의 벌점을 확인한다(시뮬레이션)
- 학생들의 벌점 상태를 배열에 기록(저장)한다.
- 총 시행 횟수 (m) 시행 결과 벌칙에 걸린 학생이 없다면 ( arr[i] < k), -1을 출력한다.
#include<bits/stdc++.h>
using namespace std;
int arr[104];
int n, m, k, target;
bool state = false;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// 최초로 벌금을 내게 되는 학생
cin >> n >> m >> k ;
for(int i = 0; i < m; i++) { // 10^8 복잡도 안넘음
cin >> target; // 벌칙에 걸린 학생의 번호
arr[target]++;
// 벌칙에 걸린 학생이 있는지 확인
for(int j = 1; j <=n; j++) {
if(arr[j] >= k) {
cout << j << "\n"; state= true;
break;
}
}
if(state) break;
}
if(!state) cout << -1 << "\n";
return 0;
}
해설코드
#include <iostream>
#define MAX_N 100
#define MAX_M 10000
using namespace std;
int n, m, k;
int penalized_person[MAX_M];
int penalty_num[MAX_N + 1];
int main() {
// 입력
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
cin >> penalized_person[i];
// 각 패널티 횟수를 세서,
// 최초로 K번 이상 벌칙을 받는 사람을 추적합니다.
int ans = -1;
for(int i = 0; i < m; i++) {
int target = penalized_person[i];
penalty_num[target]++;
if(penalty_num[target] >= k) {
ans = target;
break;
}
}
cout << ans;
return 0;
}
Challenge : 선두를 지켜라
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-keep-the-lead/description
선두를 지켜라 설명 | 코드트리
선두를 지켜라을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
이 문제의 경우 아래 3가지를 고민하는데 많은 시간이 들었습니다.
- 배열에 어떤 값을 저장하는가
- 선두 결정과 선두 바뀜의 차이
- 선두 바뀜 판정 방법
풀이 시간 : 5시간
접근 방법
- 배열에 매초마다 위치기록
- 변수에 선두를 저장하고, 배열을 탐색하면서 추월하는 순간을 카운팅
1) 1 차원 배열에 매 초마다 어느 위치에 있는지 기록
거리, 속도, 시간
문제에서 "주어지는 특정 속도로 특정 시간만큼 이동"한다고 했습니다. 그러면 결국 선두가 뒤바뀌는 것을 알기 위해서는 특정 시각에 각각의 위치를 알아야합니다.
문제에서는 속도와 시간을 주었지 "위치"는 제공하지 않았기 때문에, 거리/속도/시간 공식에 따라 거리를 구해야합니다.
여기서 구한 거리를 배열의 값으로 저장합니다.
예시) 속도 4 (m/h)를 1시간동안 이동한다.
1시간 후의 거리 = 속도 4 (m/h) * 시간 1 h = 4 m 입니다.
시간은 1시간씩 선형적으로 증가하기 때문에 거리에 대한 공식 x(t) = v * t 를 만들 수 있습니다.
코드 적용
for(int i = 0; i < m; i++) {
cin >> v >> t;
for(int j = 1; j <= t; j++) {
arr_b[cur_time + j] = arr_b[cur_time] + v * j;
}
cur_time += t;
}
틀린 이해)
필자는 1시간 동안 1/4m 만큼 이동한다고 잘못 이해했습니다.
선두가 바뀐 것을 판정하는 방법
가정 1) 두 사람이 같은 위치일 때 앞뒤 차이를 곱하여 추월 여부 판정
A,B의 시간에 따른 위치 값을 구간에 따라 표현한 1차 함수로 나타냅니다.
A 에 대한 함수 f(t), B에 대한 함수 g(t)일 때 (t는 시간을 의미하며 자연수이다), {f(t - 1) - g( t- 1 )} * {f(t + 1) - g( t + 1) } < 0 이면 선두가 바뀌었다라고 판정합니다.
반례) 연속으로 같은 값이 나온 후 선두가 바뀌는 것을 판정하지 못합니다.
테스트케이스 1에서 t = 3, 4일 때 A와 B의 값이 각각 6, 7 로 같은 값을 가지기 때문입니다. 2초, 5초의 값으로 선두가 바뀌는 것을 판정해야합니다.
여기서 더이상 방법이 떠오르지 않아 질문을 했습니다
[가정1]의 문제점
1. 두 사람의 위치가 같지 않아도, 추월이 일어날 수 있습니다.
- 1초 -> 2초로 넘어갈 때 A는 1초에서 3이고, 2초에서 10이라고 하면, B가 1초에서 1이고 2초에서 13이면 둘이 만나지 않더라도 추월이 일어날 수 있습니다.
2. 연속으로 두 사람의 위치가 같은 경우 대소 비교하기 어려움
3. 선두가 바뀌는 것 != 선두가 결정되는 것 (주의사항)
- 문제를 보면 "단, 두 사람이 공동으로 선두를 지키는 경우, 어느 한 쪽이 앞서가기 전까지는 선두가 바뀌지 않았다고 판단합니다."라고 되어있습니다. 즉 둘이 1초, 2초, 3초 같은 위치인 경우 아직 선두가 결정되지 않은 것입니다.
- 4초에서 A가 10, B가 20인경우 B가 선두로 처음 결정된 것이지 선두가 바뀐것이 아닙니다.
2) 올바른 접근방법 : 현재 앞서고 있는 사람이 누구인지 배열 변수에 기록
동점이 되는 시점을 찾아서 앞뒤를 비교하기보다, 매 초마다 "현재 앞서고 있는 사람이 누구인지" 를 변수에 기록하며 과거의 선두와 비교하는 방식이 훨씬 간단하고 확실합니다.
[참고] 토론 글 답변 받은 내용입니다. 즉, 앞서 배운 배열 기록이 활용되는 부분이었습니다. 선두인 사람을 배열에 기록하는 것이 핵심이었습니다.
#include<bits/stdc++.h>
#define MAX 1'000'004
using namespace std;
int arr_a[MAX], arr_b[MAX], arr[MAX];
int n, m, cur_time, v,t, cnt, sum_time;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m; // 시행 횟수
// A의 매초마다 이동거리
for(int i = 0; i < n; i++) {
cin >> v >> t;
sum_time += t;
for(int j = 1 ; j <= t; j++) {
arr_a[cur_time + j] = arr_a[cur_time ] + v * j; // 이전 거리에서 누적해서 더해야함.
}
cur_time += t;
}
// B의 매초마다 이동거리
cur_time = 0;
for(int i = 0; i < m; i++) {
cin >> v >> t;
for(int j = 1; j <= t; j++) {
arr_b[cur_time + j] = arr_b[cur_time] + v * j;
}
cur_time += t;
}
// 매초마다 현재 앞서고 있는 사람이 누구인지 변수에 기록하자.
// 과거의 선두와 비교하는 방식
for(int i = 1; i <= sum_time; i++) {
if(arr_a[i] > arr_b[i]) arr[i] = 1; // a가 더 빠르면 1, b가 빠른 경우 2
else if(arr_a[i] < arr_b[i]) arr[i] = 2;
else arr[i] = 3; // 같은 값을 가질 때, 선두가 바뀌지 않음
}
int head = -1;
// 선두가 결정되면 head의 값이 할당됨 3은 선두라고 할 수 없음
for(int i = 1; i <= sum_time; i++) {
// 3에서 2 or 1로 바뀐 것은 선두가 결정되었다고 하는거지 선두가 바뀌었다고 하지 않는다.
// 첫 선두 정하기
if(head == -1 && arr[i] != 3) head = arr[i]; // 첫선두가 정해질거임
if(head != -1 && arr[i] != 3 && head != arr[i]) {
cnt++; head = arr[i]; // 선두 교체
}
}
cout << cnt << '\n';
return 0;
}
해설코드
나의 풀이와 다른점
- 해설은 매초마다 서있는 위치를 기록할 때 이전 초 기준으로 속도 만큼 더함.
- 필자는 입력받은 시점의 시각 기준으로 offset으로 v*t를 더함
#include <iostream>
#define MAX_T 1000000
using namespace std;
int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];
int main() {
// 입력
cin >> n >> m;
// A가 매 초마다 서있는 위치를 기록
int time_a = 1;
for(int i = 0; i < n; i++) {
int v, t;
cin >> v >> t;
while(t--) {
pos_a[time_a] = pos_a[time_a - 1] + v;
time_a++;
}
}
// B가 매 초마다 서있는 위치를 기록
int time_b = 1;
for(int i = 0; i < m; i++) {
int v, t;
cin >> v >> t;
while(t--) {
pos_b[time_b] = pos_b[time_b - 1] + v;
time_b++;
}
}
// A와 B 중 더 앞서 있는 경우를 확인합니다.
// A가 리더면 1, B가 리더면 2로 관리합니다.
int leader = 0, ans = 0;
for(int i = 1; i < time_a; i++) {
if(pos_a[i] > pos_b[i]) {
// 기존 리더가 B였다면
// 답을 갱신합니다.
if(leader == 2)
ans++;
// 리더를 A로 변경합니다.
leader = 1;
}
else if(pos_a[i] < pos_b[i]) {
// 기존 리더가 A였다면
// 답을 갱신합니다.
if(leader == 1)
ans++;
// 리더를 B로 변경합니다.
leader = 2;
}
}
cout << ans;
return 0;
}
Challenge : 좌우로 움직이는 로봇
내풀이
풀이 시간 : 1시간
접근 방법
- A, B 로봇이 각각 매초 마다 이동하는 위치를 배열에 기록
- 두 로봇이 같은 시각에 같은 위치에 있을 때, 이전 시간에 두 로봇의 위치가 동일한지 판정 후 카운팅
실수한 부분
- char 타입 문자를 int로 선언하여 if(d == 'R') 을 수행하지 못함
- 이동이 종료하고 위치가 유지되어야함. 마지막 위치값으로 배열의 나머지 값을 초기화해야함
💡 TIP
두 로봇 A,B를 같은 시각에 한번에 이동을 처리하기 보다는 A 움직임 처리 후 B 움직임을 처리하는 것이 간편하다
매초 마다 어느 위치에 있었는지 기록하고 1초부터 쭉 탐색을 하며 시간과 위치가 동시에 일치살 때를 구한다.
#include<bits/stdc++.h>
#define MAX 2'000'000 // 최대 이동 거리를 정확히 모르겠음.
using namespace std;
int n, m, t, cur_time =1, cnt, sum_a, sum_b;
int arr_a[MAX], arr_b[MAX];
char d;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
// A의 시간에 따른 이동위치 기록
for(int i = 1; i <= n; i++) {
cin >> t >> d;
if(d == 'R') {
for(int j = 0; j < t ;j++) {
arr_a[cur_time] = arr_a[cur_time - 1] +1;
cur_time++;
}
}else {
for(int j = 0; j < t ;j++) {
arr_a[cur_time] = arr_a[cur_time - 1] -1 ;
cur_time++;
}
}
}
fill(&arr_a[cur_time], &arr_a[0] + MAX, arr_a[cur_time -1]); // 마지막 종료 후 마지막 위치값으로 나머지 초기화
// B의 시간에 따른 이동위치 배열에 기록
cur_time = 1;
for(int i = 1; i <= m; i++) {
cin >> t >> d;
if(d == 'R') {
for(int j = 0; j < t ;j++) {
arr_b[cur_time] = arr_b[cur_time - 1] +1;
cur_time++;
}
}else {
for(int j = 0; j < t ;j++) {
arr_b[cur_time] = arr_b[cur_time - 1] - 1;
cur_time++;
}
}
}
fill(&arr_b[cur_time], &arr_b[0] + MAX, arr_b[cur_time -1]);
// 배열을 탐색하면서 같은 값을 가질 때를 찾고 직전과 다른 위치인 경우 카운팅
for(int i = 1; i <= MAX; i++) {
if(arr_b[i] != 0 && arr_a[i] != 0 && arr_a[i] == arr_b[i] && arr_a[i-1] != arr_b[i-1]){
cnt++;
}
}
cout << cnt << "\n";
return 0;
}
해설코드
나의 풀이와 다른 점
- 두 로봇의 수행시간이 각각 다를 수 있기 때문에 각 로봇의 수행시간을 구하고 그 중 최댓값을 가지는 시간 만큼만 배열을 순회한다.
- 필자는 MAX = 2,000,000까지 배열을 모두 탐색하기 때문에 상대적으로 시간이 더 걸린다.
#include <iostream>
#define MAX_T 1000000
using namespace std;
int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];
int main() {
// 입력
cin >> n >> m;
// A가 매 초마다 서있는 위치를 기록
int time_a = 1;
for(int i = 0; i < n; i++) {
char d; int t;
cin >> t >> d;
while(t--) {
if(d == 'R')
pos_a[time_a] = pos_a[time_a - 1] + 1;
else
pos_a[time_a] = pos_a[time_a - 1] - 1;
time_a++;
}
}
// B가 매 초마다 서있는 위치를 기록
int time_b = 1;
for(int i = 0; i < m; i++) {
int t; char d;
cin >> t >> d;
while(t--) {
if(d == 'R')
pos_b[time_b] = pos_b[time_b - 1] + 1;
else
pos_b[time_b] = pos_b[time_b - 1] - 1;
time_b++;
}
}
if(time_a < time_b) {
for(int i = time_a; i < time_b; i++) {
pos_a[i] = pos_a[i - 1];
}
}
else if(time_a > time_b) {
for(int i = time_b; i < time_a; i++) {
pos_b[i] = pos_b[i - 1];
}
}
// 새롭게 만나는 횟수를 구합니다.
int cnt = 0;
int time_max = 0;
if(time_a < time_b)
time_max = time_b;
else
time_max = time_a;
for(int i = 1; i < time_max; i++) {
if(pos_a[i] == pos_b[i] && pos_a[i - 1] != pos_b[i - 1])
cnt++;
}
cout << cnt;
return 0;
}
Challenge : 악수와 전염병의 상관관계 2
악수와 전염병의 상관관계 2 설명 | 코드트리
악수와 전염병의 상관관계 2을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이시간 : 1시간
접근 방법
- 시간, 개발자A, B의 값을 하나로 담는 구조체 정의하여, 시간을 오름차순 정렬
- 배열에는 매 시행(T)마다 개발자마다 감염시킬 수 있는 횟수를 저장해야함 `hs[104]`
- 감염여부를 `contag[104]`에 저장
- 테이스케이스를 시간의 오름차순으로 정렬한 결과를 2명이 감염된 상태인지 아닌지 경우의 수를 나눠 탐색
실수한 부분
- 감염가능(악수 가능) 횟수를 저장하는 hs[] 에 fill() K로 초기화 해야함.
#include <bits/stdc++.h>
using namespace std;
struct contagion{
int t, x, y;
};
bool compare(contagion a, contagion b ) {
return a.t < b.t;
}
int N, K, P, T;
int t[250];
int x[250];
int y[250];
int hs[104]; // 개발자의 악수할 수 있는 횟수
int contag[104];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> K >> P >> T;
contag[P] = 1;
fill(&hs[0], &hs[0] + 104, K); // 최대 2번
vector<contagion> v;
for (int i = 0; i < T; i++) {
cin >> t[i] >> x[i] >> y[i];
v.push_back({t[i], x[i], y[i]});
}
// 시간을 기준으로 오름차순 정렬해야함.
int t_ = 0, x_ = 0, y_ = 0;
sort(v.begin(), v.end(), compare);
for(auto i : v) {
t_ = i.t; x_ = i.x; y_ = i.y;
if(contag[x_] == 1 && contag[y_] == 1) {
if(hs[x_] > 0) hs[x_]--;
if(hs[y_] > 0) hs[y_]--;
}else if(contag[x_] == 1 && contag[y_] == 0) {
if(hs[x_] > 0 ) hs[x_]--, contag[y_] = 1;
}
else if(contag[y_] == 1 && contag[x_] == 0) {
if(hs[y_] > 0 ) hs[y_]--, contag[x_] = 1;
}
}
for(int i = 1; i <= N; i++) {
cout << contag[i];
}
return 0;
}
해설코드
#include <iostream>
#include <algorithm>
#define MAX_N 100
#define MAX_T 250
using namespace std;
int n, k, p, t;
int shake_num[MAX_N + 1];
bool infected[MAX_N + 1];
// 악수의 정보를 나타내는 클래스 선언
class Shake{
public:
int time;
int person1;
int person2;
Shake(int time, int person1, int person2) {
this->time = time;
this->person1 = person1;
this->person2 = person2;
}
Shake(){}
};
// Custom Comparator
bool Cmp(const Shake &a, const Shake &b) {
// 시간을 기준으로 오름차순으로 정렬합니다.
return a.time < b.time;
}
int main() {
// 입력
cin >> n >> k >> p >> t;
infected[p] = true;
Shake shakes[MAX_T];
for(int i = 0; i < t; i++) {
int time, person1, person2;
cin >> time >> person1 >> person2;
// Shake 객체를 생성해 넣어줍니다.
shakes[i] = Shake(time, person1, person2);
}
// custom comparator를 활용한 정렬
sort(shakes, shakes + t, Cmp);
// 각 악수 횟수를 세서,
// K번 초과로 악수를 했을 시 전염시키지 않습니다.
for(int i = 0; i < t; i++) {
int target1 = shakes[i].person1;
int target2 = shakes[i].person2;
// 감염되어 있을 경우 악수 횟수를 증가시킵니다.
if(infected[target1])
shake_num[target1]++;
if(infected[target2])
shake_num[target2]++;
// target1이 감염되어 있고 아직 K번 이하로 악수했다면 target2를 전염시킵니다.
if(shake_num[target1] <= k && infected[target1])
infected[target2] = true;
// target2가 감염되어 있고 아직 K번 이하로 악수했다면 target1을 전염시킵니다.
if(shake_num[target2] <= k && infected[target2])
infected[target1] = true;
}
for(int i = 1; i <= n; i++) {
if(infected[i])
cout << 1;
else
cout << 0;
}
return 0;
}
Test : 선두를 지켜라 3
https://www.codetree.ai/ko/trails/complete/curated-cards/test-keep-the-lead-3/description
선두를 지켜라 3 설명 | 코드트리
선두를 지켜라 3을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이 1) 두 사람의 시간에 따른 위치를 매초 마다 선두인 것을 결과 배열에 기록
풀이시간 : 40분
실수한 부분
1. 공간복잡도 초과
- 배열의 인덱스는 시간이 변수인데, 위치의 최댓값을 고려해서 1,000,000,000 (= 10^9)으로 생각함. 시간 (T)의 최댓값* 횟수(N,M)의 최댓값 = 1,000,000이 올바름
- 10^9을 넘을 수 있으니 타입을 long long으로도 바꿈. 이로인해 A, B의 시간에 따른 위치 배열과 선두만 기록하는 배열 총 3개만 해도 메모리가 24GB 나오는 공간복잡도 초과 문제가 발생함
2. typedef <기존 타입> <새로운 별명타입>;
- define과 헷갈려서 앞에 #을 넣지않고, 콤마(;)를 생략했음
#include<bits/stdc++.h>
#define MAX 1'000'000 // 시간대별 위치를 기록, 위치가 MAX 의 범위가 아님. 시간임 1000 회 * 1000초
using namespace std;
int N, M, cnt;
int v[1000], t[1000];
int v2[1000], t2[1000];
int arr_a[MAX], arr_b[MAX], res[MAX];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
int time_a = 1;
for (int i = 0; i < N; i++) {
cin >> v[i] >> t[i];
// 시간에 따른 A의 위치 기록
// t초동안 1초씩 v만큼 더하면됨
for(int j = 0; j < t[i] ; j++) {
arr_a[time_a] = arr_a[time_a -1] + v[i] ;
time_a++;
}
}
int time_b = 1;
for (int i = 0; i < M; i++) {
cin >> v2[i] >> t2[i];
// 시간에 따른 B의 위치 기록
for(int j = 0; j < t2[i]; j++) {
arr_b[time_b] = arr_b[time_b -1 ] + v2[i];
time_b++;
}
}
// 1 : A, 2 : B , 3 : A, B
for(int i = 1; i < time_a; i++) {
if(arr_a[i] == arr_b[i]) res[i] = 3;
else if(arr_a[i] < arr_b[i]) res[i] = 2;
else res[i] = 1;
}
for(int i = 1; i < time_a; i++) {
if(res[i] != res[i-1]) cnt++;
}
cout << cnt << '\n';
return 0;
}
풀이 2) 결과 배열없이 매초마다 두 사람의 위치를 비교하여 현재 선두를 찾고, 이전 선두와 다른지 비교
풀이시간 : 1시간
장점
- 결과배열을 저장하는 배열이 없어져 메모리가 1MB 줄어듦
- 다시 결과 배열을 탐색하지 않아도 되어 시간이 1ms 줄어듦
실수한 부분
- 이전 선두(leader)값과 현재 선두(cur)의 값이 다를 때 개수를 카운팅(cnt++)하는데, 이때 새로운 선두를 현재 선두로 업데이트 하지않아 매우 큰 cnt 값이 생김
- `leader = cur` 이 필요했음
- A와 B의 위치를 시간순으로 비교할 때 첫 선두는 카운팅에 포함(Cnt = 1) 해야하는데, 미포함해야한다고 생각해서 조건문이 늘어남.
#include<bits/stdc++.h>
#define MAX 1'000'000 // 시간대별 위치를 기록, 위치가 MAX 의 범위가 아님. 시간임 1000 회 * 1000초
using namespace std;
int N, M, cnt=1;
int v[1000], t[1000];
int v2[1000], t2[1000];
int arr_a[MAX], arr_b[MAX];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
int time_a = 1;
for (int i = 0; i < N; i++) {
cin >> v[i] >> t[i];
// 시간에 따른 A의 위치 기록
// t초동안 1초씩 v만큼 더하면됨
for(int j = 0; j < t[i] ; j++) {
arr_a[time_a] = arr_a[time_a -1] + v[i] ;
time_a++;
}
}
int time_b = 1;
for (int i = 0; i < M; i++) {
cin >> v2[i] >> t2[i];
// 시간에 따른 B의 위치 기록
for(int j = 0; j < t2[i]; j++) {
arr_b[time_b] = arr_b[time_b -1 ] + v2[i];
time_b++;
}
}
// 1 : A, 2 : B , 3 : A, B
int leader = 0, cur = 0;
if(arr_a[1] == arr_b[1]) leader = 3 ;
else if(arr_a[1] < arr_b[1]) leader = 2;
else leader = 1;
for(int i = 2; i < time_a; i++) {
if(arr_a[i] > arr_b[i]) cur = 1;
else if(arr_a[i] < arr_b[i]) cur= 2;
else cur = 3;
if(cur != leader) cnt++, leader = cur; // 리더를 현재인 값으로 업데이트
}
cout << cnt<< '\n';
return 0;
}
해설코드
#include <iostream>
#define MAX_T 1000000
using namespace std;
int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];
int main() {
// 입력
cin >> n >> m;
// A가 매 초마다 서있는 위치를 기록
int time_a = 1;
for(int i = 0; i < n; i++) {
int v, t;
cin >> v >> t;
while(t--) {
pos_a[time_a] = pos_a[time_a - 1] + v;
time_a++;
}
}
// B가 매 초마다 서있는 위치를 기록
int time_b = 1;
for(int i = 0; i < m; i++) {
int v, t;
cin >> v >> t;
while(t--) {
pos_b[time_b] = pos_b[time_b - 1] + v;
time_b++;
}
}
// A와 B 중 더 앞서 있는 경우를 확인합니다.
// A가 리더면 1, B가 리더면 2, 둘 다 리더면 3으로 관리합니다.
int leader = 0, ans = 0;
for(int i = 1; i < time_a; i++) {
if(pos_a[i] > pos_b[i]) {
// 조합이 바뀌었다면
// 답을 갱신합니다.
if(leader != 1)
ans++;
// 리더를 A로 변경합니다.
leader = 1;
}
else if(pos_a[i] < pos_b[i]) {
// 조합이 바뀌었다면
// 답을 갱신합니다.
if(leader != 2)
ans++;
// 리더를 B로 변경합니다.
leader = 2;
}
else {
// 조합이 바뀌었다면
// 답을 갱신합니다.
if(leader != 3)
ans++;
// 리더를 둘 다로 변경합니다.
leader = 3;
}
}
cout << ans;
return 0;
}
'Algorithm' 카테고리의 다른 글
| [CodeTree] Ch5.시뮬레이션 2 - dx dy technique (0) | 2026.06.09 |
|---|---|
| [CodeTree] 5회차: 북마크로 틀린 문제, 삽질한 문제 복습하는 습관 만들기 (0) | 2026.06.07 |
| [CodeTree] Ch5.시뮬레이션 2 - 최장 연속 부분 수열 (0) | 2026.06.01 |
| [CodeTree] 4회차: 코테 꾸준히 하고자 하는 습관을 지켜주는 환경 (feat. 학습 리마인더 알림톡) (0) | 2026.06.01 |
| [CodeTree] Ch4. 시뮬레이션1 - 사각형 칠하기 (0) | 2026.05.26 |