Programmers [2 x N 타일링]

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n) {
	int  a = 1,b=2, temp;
	if (n == 1) { return a; }
	if (n == 2) { return b; }
	for (int i = 0; i <n-2; i++) {
		temp = a;
		a = b;
		b = (a + temp) % 1000000007;
	}
	return b;
}

종이에 적다가 피보나치 각이 보여서 썼더니 틀렸다.

근데 맞는거같아서 막 종이에 적어보니 맞네?

왜지.... 하던 도중 1~~~~0007로 나누라는 거 보니까 어마어마한 숫자인 것 같고 그러면 overflow날 거 같아서 longlong으로 변경하고 테스트를 하니 그래도 숫자가 좀 커지만 터지는 현상이 발견...(범위가 60000까지인가 그럽니다)

 

왜 끝을 7로 한것인지 모르겠다. 100000000 같이 되어있으면 윗자리를 날린다고 생각할 수도 있는데, 7이니까 중간에 나눠주면 문제가 생기는 게 아닐까 싶었지만 일단은 잘 돌아가니 패스가 되었다.

 

(a+b+c)% d 

((a+b)% d+c)% d

 

두 꼴이 같다는 것인데.... 이건 분배 법칙도 아니고 뭔 마법 같은 일인지 허허

사실 % 는 나누기라기보다는 뺄 샘이라고 생각하면 쉽게 이해할 수 있을지도 모른다.

나중에 (a+b+c)를 되는대로 빼는 것과 틈틈이 시간 날 때마다 빼주는 거라 생각하면.....

 

납득.

 

p.s.(사실 본문)

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n) {
	int answer = 0;
	vector<int> ind;
	for (int i = 0; i <= n/2; i++) {
		ind.clear();
		for (int j = 0; j < n-i*2; j++) {ind.push_back(0);}
		for (int j = 0; j < i; j++) {ind.push_back(1);}
		do { answer++;} while (next_permutation(ind.begin(), ind.end()));
	}
	cout << answer % 1000000007;
	return answer % 1000000007;
}

사실 처음 구현한 코드는 위와 같다.

 

'가로로 놓을 거냐', '세로로 놓을 거냐' 이 두 가지의 결정이기 때문에 순열을 생각해서 permutation을 사용한 코드.

 

가로로 놓는 경우가 최대 n을 2로 나눈 만큼 존재할 수 있기 때문에 for문을 n/2까지 돌렸다.

세로를 0, 가로를 1로 vector에 넣고 순열을 지지고 볶고 하는 느낌인데,

 

짤 때는 아이디어 잘 뽑아낸 거 같다 라고 생각했다.

 

next_permutation의 경우 복잡도는 거의 n이라고 어디서 주워 들었고 대충 복잡도를 계산하면

 

for문 n/2+1

permutation n*3/4 (모두 세로일 경우 n개, 모두 가로일 경우 n/2개임으로 평균 잡았음)

 

이라고 생각해서 n^2(3/8)이겠구나.... 했지만?

 

 

 

 

 

한번 다음 순열을 연산하는 게 n이라는 거지 경우의 수가 100가지면 100n이 되어버린다.

그 경우 피보나치수열은(한 칸씩 밀려있는 것은 위의 문제의 경우를 가정해서이다. [2칸이면 2가지 경우])

1	2	3	4	5	6	7	8	9	10	11
1	2	3	5	8	13	21	34	55	89	144

처음에는 몰라도 나중에는 n^2이.. 더 큰 경우는 답도 없는 큰 형님이 되신다.

 

즉, 코딩 시험에서 n^2(3/8)에 큰 형님을 곱하게 되면 (참고로 40번째 피보나치수열은 102,334,155로 1억을 넘긴다)

결과를 볼 때쯤이면 아마 다른 사람이 면접이 끝나고 결과가 발표가 나더라도 당신은 아직 답이 없는 검은색 창을 응시하고 있게 될 것이다.

 

아쉬워서 복잡도라도 계산해보자고 해본 글이다.

영양가가 있는지는 미지수...

 

p.s의 p.s.

30개의 permutation의 연산 횟수는 1346269이고 이에 따른 수행 시간을 유추해본다면

30*30*3/8*1346269= 454,365,787.5...

초당 1억의 연산이라 가정하면 얼추 4.5초 안에 결과가 나올 것으로 예상된다.

(permutation의 연산 횟수를 15일 때부터 30까지 다르게 고려를 해줘야 하지만 그것까지 하면 너무 내 머리가 과부하가 올 것 같다, 얼추 조금 덜 걸린다... 정도로만 생각해두자.)

 

그리고 3초가 걸린다. ( 만족할만한 결과인지 모르겠음..)

 

좀 더 정확한 복잡도 계산을 하고 싶은데 아직 내공이 부족한 것 같다.