풀이

: 다시 풀어야 함. - 220927

어떻게 풀어야 할까?

• 연속적인 것이므로 투포인터
• 경우의 수를 어떻게 처리할 것인가?

문제 요구사항

: 길이가 n개인 수열 중, 연속한 1개 이상의 수를 뽑았을 때,
동일한 수가 여러번 등장하지 않는 경우의 수는?

첫번째 풀이 전략

• 1번) 1 에서부터 마지막 2번까지 길이를 하나씩 늘려나가면서 동일한 것이 있는지를 체킹 하면서 카운팅을 함.
  : start : 0 / end : 4까지 도달함.

• 2번) 그리고 start를 1증가하고, end = start로 만듦.
  다시 1번과 같이 진행

• 3번) 이를 반복적으로 하다가 start가 n이 되면 종료하는 식으로 함.

결과

: 시간 초과

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#include <iostream>
// 14:13 ~ 

int num[100001];
bool check[100001];

int n;

vector<int>v;

int ret = 0;


int main()
{
	
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> num[i];
	}
	
	// 연속된 것이므로 투포인터로 가야함. 

	int start = 0;
	int end = 0;

	// 내 생각에는 0번 인덱스 기준으로 놓고, 마지막까지 진행
	// 이후 마지막 n - 1에 도달하면 start를 1증가, end를 start 로 위치
	// 다시 진행.

	
	while (start <= end)
	{
		fill(check, check + 100001, false);
		bool nope = false;

		for (int i = start; i <= end; ++i)
		{
			if (check[num[i]] == true)
			{
				nope = true;
				break;
			}
			else
				check[num[i]] = true;
		}

		if (nope == false)
		{
			++ret;			
		}
		++end;

		if (end == n)
		{
			++start;
			end = start;
		}

		if (start == n)
			break;
	}

	cout << ret << endl;

}

큰돌님 풀이 전략

• 1) 나의 풀이전략 1번과 같이 길이를 증가하면서 진행해 나감.
• 2) 그러다가 만약에 이미 체크된 값이 true를 발견한다면?
  여기서 끝내고, start 를 + 1하고 다시 진행함.
  

  : 1 , 2 , 3까지 진행후, 1231에서 끝.
  2부터 시작해서 231 진행하다가 2312 끝
  이런식으로 하자는 의미임.

등차 수열의 합.

3,1,2,4 를 갯수로 나타낼수 있는 공식이 있음.
: 등차수열의 합을 사용하면 됨.

• 참고자료 보고 정리 .

경우의 수 문제가 나오면?

: 일단 자료형을 long long으로 디폴트 처리하자.

나열되는 수의 경우의 수를 어떻게 카운팅할지를 생각해야 함.

1,2,3,4,5 - 5개 카운팅
2,3,4,5 - 4개 카운팅
3,4,5 - 3개 카운팅
4,5 - 2개 카운팅
5 - 1개 카운팅.
=> 결과 15개
해당 수열을 나타낼수 있는 모든 경우의 수에 대해 생각을 해보아야 함.
1,2,3
2,3,1
3,1,2
1,2
2
=> 결과 12개
1
1
1
1
1
=> 결과 5개

경우의 수를 어떻게 표현해야 할까 고민이 된다면, 일단 예제의 결과를 나열한 다음에 생각을 해보자.

: 수열의 시작값 변경하지 전에
ret += (end - start);

• 위의 출력을 토대로 구현할 수 있는데, 못했음.