전체 글98 [17406번] 배열 돌리기4 17406번: 배열 돌리기 4 www.acmicpc.net 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 회전연산 이란, 아래 그림 처럼 배열을 회전시키는 연산이다. 주어진 회전 연산의 정보에 따라 회전한 배열 A의 값중 최소값을 출력하는 문제다. 구현력을 보는 문제인듯 하다. 1. 회전 연산의 순서를 정하고 (순열)2. 정해진 순서에 맞춰 회전 연산을 수행 (회전)3. 연산이 끝난 배열의 값을 구해서 최소값을 구한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676.. 2020. 4. 11. [17471번] 게리맨더링 17471번: 게리맨더링 www.acmicpc.net 1. 각 지역들이 어느 선거구에 포함될지 정한다. (조합) 2. 나눠진 선거구안의 지역들을 bfs하면서 서로 이어져 있으면 union find를 이용해 묶어준다.3. 각 선거구 지역들이 다 이어졌으면 두 선거구의 인구차를 구해서 최솟값 갱신을 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112.. 2020. 4. 11. [17472번] 다리 만들기2 17472번: 다리 만들기 2 www.acmicpc.net 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139#include #include #include #include #include #define pii.. 2020. 4. 11. 5607. 조합 n^{p} \equiv n \left(\text{mod}\ p \right) N combination R의 값을 1234567891로 나눈 나머지를 출력. 즉, 우리에게 익숙한 nCr을 1234567891로 나눈 나머지를 출력하란 말이다. nCr을 구하는 공식을 보면 이다. 하지만 나머지 연산은 나눗셈에 적용할 수 없다. 그래서 이 식을 곱셈 형태로 바꿔줘야 하는데 여기서 사용되는 것이 페르마의 소정리이다. 페르마의 소정리에 의해서 P를 1234567891이라고 하면 가 성립한다. 제곱의 경우는 분할 정복을 통해서 O(logP)의 시간복잡도 안에 해결할 수 있기 때문에 해결이 가능하다. 123456789101112131415161718192021222324252627282930313233343536373.. 2020. 4. 4. 이전 1 2 3 4 5 6 7 ··· 25 다음