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
의외로 고민했는데 원인이 되게 의미없는거엿다 테스트케이스가 하나밖에 없어서 좀 고민한 문제이다. https://www.acmicpc.net/problem/1059 1059번: 수2 첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다 www.acmicpc.net 일단 첫번째 코너케이스 1 3 1 과 같은 경우에는 0을 가상의 left값으로 잡고 문제를 해결하면 된다. 두번째 1 998 999 과 같은 경우에는 1001을 가상의 right값으로 잡고 문제를 해결하면 된다 세번째 4 1 3 5 7 3 N이 Lucky Set 안에 있는 경우 답은 항상 ..