8월 11일

10971번 외판원순회2

외판원순회2 N제한이 상당히 작으므로 모든경우 탐색하기를 이용해서 푼다.  N이 작다는건 10이하 정도일때를 말하고 10!정도가 작은수 이기 때문이다.

c++에서 입출력 속도를 높이려면 ios_base::sync_with_stdio(false);를 처음에 선언하면 된다.

2차원 벡터선언 헷갈리는데 vector< vector<int> > a(n,vector<int>(m)); 이렇게 하면된다.

벡터인데 그 안에 벡터가 있는 거고 초기값으로 n개의 vector<int>(m) 가 들어있다.

6603번 로또

#include<algorithm>을 이용해 순열을 쉽게 풀수 있는데 중복 순열 또한 쉽게 풀린다.

예를 들어 0 0 1 1 이런식으로 중복된 숫자가 있어도 알아서 순열을 잘 만들어 준다.

참고로 경우의 수는 n! / a! * b! 이다. n은 전체 수 a , b 는 중복된 수들의 갯수들 여기선 a=2 b=2 가 되겠다.

무튼 이렇게 하고 k개중에 6개를 뽑아야한다. 중복순열을 이용한다.

S에 0을 6개, 1을 k-6개를 넣는다.

그럼 S는 0 0 0 0 0 0 1 1 1 ... 이렇게 된다.

여기서 S를 순열로 계속 돌리면서 가능한 모든 조합을 뽑는다.

번호는 스몰 s에 저장하고 S의 순열을 돌리면서 0인 인덱스의 s값을 출력하면 된다.

말 그대로 순열로 풀면된다. 

0 0 0 0 0 0 1

0 0 0 0 0 1 0

0 0 0 0 1 0 0

0 0 0 1 0 0 0

0 0 1 0 0 0 0

0 1 0 0 0 0 0

1 0 0 0 0 0 0

예를들어 숫자가 7개면 저런식으로 조합이 나올거고 저기서 0인 것의 인덱스만 빼오면 된다.

1697번 숨바꼭질

어떤 한 점에서 시작해서 +1 -1 *2를 해서 원하는 점 까지 가는데 몇번 연산을 해야하는지 찾는것이다.

이는 bfs이다. bfs는 시간복잡도가 노드의 수에 비례하기 때문에 

1. 문제에 나와있는 상태의 갯수가 적어야한다. (1초안에해야댐)

2. 최소를 구하는 문제

3. 간선의 가중치가 모두 1이다. 

이 문제를 bfs로 풀어보자.

처음 점을 큐에 집어넣고 거리를 0으로, 그리고 방문했다고 체크하고 하나씩 뺀다. 뺀 점을 now라고 하자.

now의 +1 -1 *2를 하면서 방문했다고 체크하고 now의 +1, -1 *2들을 다시 넣는다. 이때 거리를 적어놔야하는데 배열을 하나 만들어서

dist[temp] = dist[now]+1; 이런식으로 체크를한다. 반복문을 큐가 비어있지 않을때까지 계속하고

dist[m]을 출력하면 된다.

1963 - 소수경로

c++에서 memset(주소,초기값,사이즈)를 하려면 #include(cstring)을 해주자.

이 문제도 간단하다. 어떤수를 입력받고 그 수의 일,십,백,천의 자리를 바꿔가면서 원하는 수에 도달하는데 얼마나 걸리냐를 묻는다.

이것도 

1.상태의 갯수 10000개도 안된다. (1000~9999)

2.최소를 구하는 문제

3.간선의 가중치가 모두 1이다(1000에서 1001로 가는것도 1 1000에서 1010으로 가는것도 1)

이 문제를 bfs로 풀어보자.

큐에 집어 넣어서 계속 풀면된다.

일의자리에 대해서만 하면

temp = now /10 * 10해서 일의자리를 0으로 만든다

왜냐하면 예를들어 1234가 들어왔을때 1230부터 반복문을 돌려서 1230 1231 ... 1239까지 반복하면되니까

그리고 방문했는지, 소수가 맞는지 확인하고 만족한다면

방문했다고 표시하고

최단거리도 갱신하고

큐에 푸시해준다.