statechange의 업데이트는 %2가 아닌 statechange = 1-statechange로 쓰는 것이 편합니다.
44~47줄이 예외를 찾기 아주 까다로운 상황을 만들어냅니다. arr1[i][j]는 이미 0으로 초기화했으니 앞의 조건은 의미가 없고, 뒤의 마지막으로 계산한 arr1[1-state][i][j] == 0만을 검사하는데 이것이 0이라고 곱셈 후 arr1[i][j]를 바로 결정할 수는 없습니다. 초기화 문제는 arr1이 0인지가 아닌 현재 사용하는 비트가 최초인지를 검사하도록 해야 합니다. (또는 맨 처음에만 arr1을 단위행렬로 초기화하면 됩니다)
지금은 아마 문제없긴 한데 38줄과 같이 실수형을 사용하는 log, pow 등을 int에 바로 대입하면 +-1 정도 오차가 생기기 쉽습니다. 어차피 bit<<=1당 log ++이므로 bit와 log를 따로 업데이트하거나 아예 bit = 1LL << log로 정수를 통해 계산하는게 좋습니다.
tsi03136 2년 전
long long 으로 반복제곱할 횟수의 크기를 입력받았습니다.
[0] = x^1, [1] = X^2, [2] = X^4, X^8, X^16, X^32 ... [N-1] = X^(2^N) 을 반복하며 배열에 저장해 둡니다.
그리고 다음은 계산에 적용한 방법입니다.
제곱해야 할 특정 값이 들어왔을 경우 ex) 1932
비트 연산을 위해 1932 를 0111 1000 1100 으로 인식합니다.
0001부터 0010 => 0100 => 1000 ... 반복하며 1932를 구성하는 비트를 순회합니다.
첫 번째로 0100를 찾으면 log2(4) = 2, 첫번째로 곱하는 것이기 때문에 배열 2번째에 저장된 행렬값을 [1,1,1,... ,1] 에 곱합니다.
다음으로 1000을 찾으면 log2(8) = 3, 배열 3번째에 저장된 행렬값을 기존 값에 곱합니다.
1932는 각 자리 비트들이 더해져서 나온 값이지만 이 문제는 1932번 곱해야하기 때문에 이런 식으로 풀었습니다.
따라서 Big-O(log2(N)) 의 시간 복잡도를 가지는데
문제는 채점을 시작하자 마자 틀립니다.
https://matrixcalc.org/ko/#%7B... 행렬 계산 사이트를 통해 여러 케이스를 시도해보았는데 모두 문제 없어서
특이한 테스트 케이스가 입력되어있는 것 같은데 예측이 되지 않습니다....
혹시 짐작 가시는 분이 계시면 알려주시면 정말 정말 감사하겠습니다....!!!