3955번: 캔디분배 - 선형 다오판토스 방정식, 확장 유클리드 알고리즘 구매하고 싶은 캔디는 K*X+1개이며 사탕 한 봉지에 사탕이 C개 들어있을 때 몇 봉지를 사야할 지 묻는 문제이다. 이 때 이를 수식으로 적어보면 K*X+1 = C*N가 되며 이 수식을 만족하는 10^9이 넘지 않는 N을 구해주면 된다.K*X+1 = C*N는 C*N - K*X = 1로 변환 될 수 있다. 이 형태는 일차부정방정식의 형태로,먼저 선형 다오판토스 방정식에 의하여 일차부정방정식 ax + by = c이고 d = gcd(a, b)라 할 때d | c 즉 c를 d로 나누었을 때 나누어떨어지지 않는다면 해가 존재하지 않으며,그렇지 않다면 해가 무수히 존재하며 이 수식을 만족하는 하나의 특수 해를 구한다면 일반 해를 구해낼 수 있다..
1837번: 암호제작 - 문자열의 나머지 구하기 P와 K를 입력받아 P라는 숫자가 소수 p,q의 곱으로 나타내질 때,p와 q 중 하나라도 K보다 작은 p, q가 있을 경우 BAD와 두 소수 중 작은 소수를 출력하고없을 경우 GOOD을 출력하면 되는 문제이다. 간단하게 생각해보면 K범위가 10^6까지 이므로 10^6까지의 모든 소수를 에라토스테네스 체를 이용하여 구한 뒤P라는 수에 그 소수들을 하나하나 나누어 본 뒤 하나라도 나누어진다면 BAD,안나누어진다면 GOOD을 출력하면 되는 간단한 문제이다. 이 때 문제가 되는 부분은 P의 범위가 10^100으로 int, long long 자료형으로는 받을 수 없기에이를 문자열을 사용해서 받아야한다. 이 때 문자열을 정수로 나눈 나머지를 나머지 연산을 이용하여re..
A - Balloons 서로 packet을 나누어 가질 때 하나 이상의 packet을 가지며 packet에 들어있는 풍선의 수는 같지 않게 해야할 때어떤 packet의 인덱스를 가져갔는 지 출력하는 문제이다.N이 1일 때에는 무조건 한 명은 packet을 받지 못하니 불가능하고packet에 있는 풍선의 수들을 정렬한다면 가장 적은 수의 풍선이 든 packet은 N이 2일 때를 제외하고는나머지 packet들의 풍선을 더했을 때보다 무조건 적다는 것을 알 수 있다.그러므로 N이 1 또는 N이 2이며 두 packet에 들어있는 풍선의 개수가 같은 경우는 -1,아닌 경우에는 풍선이 가장 적은 packet을 제외한 packet의 인덱스 번호를 출력해주면 된다.인덱스 번호를 출력해야함을 조심하자 B - Cuttin..
A - Game Shopping 간단한 구현 문제로, 게임의 가격을 보면서 지갑에 있는 돈으로 게임을 살 수 있을 경우 지갑의 인덱스를 증가시킨다.이 때 지갑의 인덱스가 최대 인덱스만 넘어가지 않도록 처리해주면 풀 수 있는 문제이다. B - Minimum Ternary String 0과 1, 1과 2만 위치를 바꿀 수 있으며 이 때의 사전 순으로 가장 앞에 있는 문자열을 출력하는 문제로1은 무조건 바꿀 수 있다는 아이디어를 이용하여 1의 개수와 첫 2 뒤에 있는 0의 개수를 세어준 뒤,첫 2 뒤에 있는 0의 개수만큼의 '0' + 전체 문자열에서의 1의 개수만큼의 '1' + 남은 문자열을 출력해주면 되는 문제이다. C - Annoying Present 처음에 0으로 초기화된 n개의 칸으로 구성된 배열로 시..