www.acmicpc.net/problem/20309 20309번: 트리플 소트 $N$은 $3, 4, 5$ 중 하나이다. www.acmicpc.net 생각의 전환 이 문제를 풀기위해서 반드시 사고해야할 점은 "세개를 동시에 뒤집는 것" 이 무엇을 의미하는지 알아야한다 세개를 동시에 뒤집게 되면 세개 중 가운데에 있는 수는 항상 제자리에 있게 되고, 결과적으로 보자면 i 번째 수를 i+2번과 바꾸는것과 같게 되어서 홀수자리는 홀수자리끼리만 / 짝수자리는 짝수자리끼리만 바꿀수 있게 됩니다. 따라서 홀수자리에 짝수가 나온다면 절대 바꿀수 없으므로 NO, 아니면 YES를 출력하게 짜주면 됩니다. #include int arr[345678] = {0}; int main(){ int n; bool ans = tru..
https://www.acmicpc.net/problem/8464 8464번: Non-Squarefree Numbers Your program should output one integer, the n-th non-squarefree number. www.acmicpc.net 1577번의 정확히 정 반대에 해당하는 문제. 조금만 수정해줘도 쉽게 AC를 받을 수 있다. --- 소스코드 내립니다 --- setup이나 f함수의 역할은 같고, 기존의 f 함수는 k 이하의 squarefree number의 수를 세기 때문에, mid - f(mid)를 통해서 mid 이하의 non-squarefree number의 수를 세줄 수 있다. 그리고 탐색범위가 k의 영향에서 벗어나는지 WA가 나와서 그냥 e에 엄청 큰 수 ..
https://www.acmicpc.net/problem/1557 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net 생각하는데 오래걸린 문제 처음에 위의 사진처럼 엄청 무식하게 접근했다가 조언을 받아서 뫼비우스 함수라는 걸 이용해서 문제를 해결했다. 인터넷에서 찾은 분이신데, 뫼비우스 함수를 코드와 함께 깔끔하게 정리해주셨다. https://ohgym.tistory.com/19 포함과 배제, 그리고 뫼비우스 함수 INTRO 적당히 꼼수를 써가면서 풀었는데 수학적..
페르마의 소정리 사용 문제. https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 페르마의 소정리에 대해서는 백준님이 깔끔하게 정리해 주셨습니다. https://www.acmicpc.net/blog/view/29 페르마의 소정리를 통해 역원을 구해주면, 역원의 곱을 통해 나눗셈을 대체할 수 있으며, 따라서 mod연산을 할때 나눗셈을 하지않고 구할수 있게 됨. 쿼리가 10만개를 넘기 때문에, O(logN)시간에 제곱연산을 수행해주는 함수 pow를 직접 작성..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 정올같은데에서 본거같은 문제이다. #include #include #include #include char arr[11][10]; int table[128] = {0}; // 문자 - 숫자 대응 배열. int main(){ int n,tmp,sum=9,ans=0; scanf("%d", &n); for(int i=0; i
무난하게 풀었다. https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 쇠막대기를 레이저로 자를때, 앞에서 센 '(' 의 개수 = 쇠막대기의 수 만큼 기존 막대기가 분리가 되며, ')'를 통해 쇠막대기가 끝남을 알릴때도 잘린곳 - 쇠막대기의 끝 으로 이어지는 쇠막대기가 하나 더 생기기 때문에 이부분만 잘 처리해주면 AC가 나온다. #include #include char input[123456] = {0}; int main(){ int ans=0; int su..