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..
실버작 겸 감을 잃지않기위해 무난한난이도 문제를 풀고있다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 방문여부를 검사하는 visit배열을 만들어서 탐색후 visit배열에 남은 방문한곳들을 더하고 마지막으로 처음 시작한 1을 빼주면 AC. #include #include using namespace std; vector arr[101]; int visit[101] = {0}; void search(int node){ for(int i=0; i