With The Lights Out

대략 황당했던 문제. 처음에 보고 이걸 어떻게 풀어야 하나 생각했다. 진법에 맞게 -2 로 나누되, 컴파일러의 양수 / 음수 , 음수 / 양수 나눗셈에 대한 이해를 요하는 문제였다.  C/ C++ 컴파일러에서는  13 / -2  가 -6 이 나오고, 파이썬에서는 13 / -2 가 -7 이 나온다고 알려져 있다. 이는 컴파일러의 계산 차이에서 오는 것인데, 우리가 -2로 나눌 때 나머지가 음수가 나오면 진법에 적용을 할 수 없으므로 13 / -2 는 (-2) * ( -6)  + 1 으로 나타내야 한다. 예시인 -13 을 예시로 들어보자. -13 / -2 -> (-2) * 7  + 17 / -2   ->  (-2) * (-3) + 1-3  / -2 -> (-2) * (2) + 12  /-2 ->  (-2) ..

문자열을 통해 출력해 주어야 한다. 수의 길이가 333334 까지 나올 수 있으므로 범위는 long long의     -2^63 (-9,223,372,036,854,775,808) 에서 2^63 - 1(9,223,372,036,854,775,807)  를 아득히 뛰어넘는다.  따라서 아래와 같이 코드를 짜면 한 변수에 굳이 값을 저장할 필요 없이 출력 가능하다.  #include #include using namespace std;int main(void) { string eight; string two[8] = { "000", "001", "010", "011", "100", "101", "110", "111" }; int temp; cin >> eight; for (int i = 0; i

유클리드를 O(n)만큼 시도해야 한다는 것에 주의. #include #include #include using namespace std;int Euclid(int a,int b){ if (b == 0) return a; else return Euclid(b, a % b);}int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int N, S; cin >> N >> S; vector v; if (N == 1) { int input; cin >> input; cout > input; v.push_back(abs(input - S)); } sort(v.begin(), v.end()); int tmp = v[0]; for (int i =..

유클리드 호제법을 통한 풀이. 자료형 범위에 주의한다. #include #include using namespace std;int Euclid(int p, int q){ if (q == 0) return p; else return Euclid(q, p % q);}int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n; long long arr[101]; cin >> n; for (int i = 0; i > num; for (int j = 0; j > input; arr[j] = input; } long long cnt = 0; for (int a = 0; a

조합 공식과 정수론을 이용해 해결하는 문제. 조합 공식은 nCr n! / (n-r!) r! 이다.  그리고 10을 구성하는 소인수는 2 x 5 인데, 2와 5 소인수 중 개수가 작은 것이 0의 개수가 될 것이다.  팩토리얼의 소인수를 구하는 방법은 https://blog.naver.com/shalska1234/50087466089 계승(factorial, !)의 소인수분해!계승 [階乘, factorial] 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다....blog.naver.com 이 블로그 게시글을 참고했다.  100! -> 100 / 2, 100 / 4, 100/ 8 , 100 / 16  , 100 / 32 , 100 / 64 의 값을 모두 더하면 2의 소인수 개수가..

에라토스테네스의 체를 사용하여 소수를 판별 한 뒤, 출력한다.에라토스테네스의 체란 i 의 배수들을 제거해 나가며 소수를 판별해 나가는 방법인데, 시간 복잡도가 O(N log(logN)) 이다.iostream과 stdio.h 가 동기화 되어 있을 때는 cout 을 통한 출력 속도가 느림에 주의하자.  #include #include using namespace std;int check[1000001] = { false };void Primearr(int input){ for (int i = 2; i > input; if (input == 0) break; bool can = false; for (int i = 3; i

#include #include using namespace std;int main(){ string input; cin >> input; stack s; for (int i = 0; i = 'A' && input[i]

#include #include using namespace std;int arr[26];int trans(char input){ return arr[input - 'A' ];}double cal(double a, double b, char oper){ switch (oper) { case '+': return a + b; break; case '-': return a - b; break; case '*': return a * b; break; case '/': return a / b; break; }}int main(){ int N; cin >> N; string input; cin >> input; stack s; for (int i = 0; i > tmp; arr[i] = tm..

#include #include #include using namespace std;int main() { int N; int* arr; int* NGF; cin >> N; arr = new int[N+1]; int cntarr[1000001] = {0,}; NGF = new int[N+1]; for(int i = 1 ; i > input; arr[i] = input; cntarr[input] += 1; } stack s; for(int i = 1; i

스택을 이용해 풀이하는 문제, 시간 제한이 1초이므로 1억번 이상의 연산은 불가능하다.    #include #include #include using namespace std;int main() { int input; cin >> input; stack s; stack result; int arr[1000000] ; for(int i = 0 ; i > tmp; arr[i] = tmp; } for(int i = 0 ; i arr[s.top()]) { arr[s.top()] = arr[i]; s.pop(); } else ..