4317. 항구에 들어오는 배 - D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMedCxalW8DFAXd#

SW Expert Academy

최근들어 왜 이렇게 문제 이해를 잘 못하는지 모르겠습니다. 이 문제가 바로 그 문제입니다.

 

문제를 잘 못 이해하고 다른 방식으로 풀다가 오답 몇 번 맞고, 알아보니 제가 잘 못 이해한 걸 알게 되었습니다.

 

문제를 어렵게 보는 것도 능력인거 같습니다. 쓸데없는

---

이 문제는 결국 1에서 시작하는 주기가 몇 개 있는 지를 파악하는 문제입니다. 저는 이 주기를 안 보고 즐거운 날의 간격만 신경쓰면서 문제를 풀어서 틀렸습니다.

 

1에서부터 주기가 있다는 것은 결국 1에서 시작해서 n이라는 주기로 방문되는 숫자들이 있을 것이고 그 것을 방문처리를 하고 전체 탐색을 하면 가볍게 풀 수 있다는 뜻입니다.

 

그냥 제가 바보 같이 굴었던 것이죠.

 

그렇다면 그 주기와 그 주기에 마지막으로 방문했던 지점, 현재 지점을 기록할 수 있는 변수가 필요합니다.

 

현재 지점이야 저희가 for문을 도니까 바로 알 수 있는 것이고, 주기와 마지막으로 방문했던 지점만 유지하면서 for문을 돌면 되겠습니다.

#include <stdio.h>
#include <malloc.h>

int main(void) {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		// 입력
		int N;
		scanf("%d", &N);
		int* arr = (int*)malloc(sizeof(int) * N);
		for (int n = 0; n < N; n++) {
			scanf("%d", &arr[n]);
		}

		// 풀이
		int* vis = (int*)malloc(sizeof(int) * N);
		for (int n = 0; n < N; n++) {
			vis[n] = 0;
		}
		int result = 0;
		
		for (int i = 1; i < N; i++) {
			if (vis[i] == 0) {
				int temp = arr[i] - 1;
				int value = arr[i];
				result++;
				for (int j = i + 1; j < N; j++) {
					if (arr[j] - value == temp) {
						value = arr[j];
						vis[j] = 1;asdasdasd
					}
				}
			}
		}
		printf("#%d %d\n", t, result);
	}
}

---

이상 4317. 항구에 들어오는 배 - D3였습니다. ^_^