코딩하기 좋은날

https://www.acmicpc.net/problem/2909 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 캔디의 가격과 상근이가 가진 금액의 단위를 입력받아 그 단위에 맞게 반올림 하는 문제입니다. 캔디의 가격을 상근이가 가진 금액의 단위로 나눈뒤 그 몫에 다시 상근이가 가진 금액을 곱하면 반올림 하는데 사용 할 수 있는 금액이 나옵니다. 예를 들어 상근이가 100원짜리를 가지고 있고 사탕이 150원이라면 위의 연산을 시행하면 100원이 됩니다. 이때 상근이가 가진금액의 단위의 1/2보다 사탕 가격을 상근이가 가진돈으로 %연산 했을때가 크면 위로 올라가고 작으면 밑으로 내려갑니다. 다음은 코드입니다. #include using namespace std; int main(void) { ios_..

https://www.acmicpc.net/problem/1002 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 두 좌표와 거리를 입력받아서 류재명의 위치를 찾는 문제입니다. 저는 두원이 존재한다고 생각하고 가능한 모든 경우를 따져서 문제를 해결하였습니다. 가능한 경우는 총 7가지로 첫번째로 두원이 동일한 원인경우 가능한 가지수는 무한대 입니다. 두번째로 두원의 좌표는 동일하고 반지름은 다를경우 가능한 가지수는 0입니다. 세번째로 한원이 하나의 원안에 들어가 있는데 중심은 다른경우 입니다. 이경우는 가능한 가지수가 0입니다. 네번째는 하나의 원이 하나의 원안에 들어가있고 중심이 다르면서 하나의 점에서 만나는 경우입니다. 이경우 가능한 가지수는 1입니다. 다섯번째 경우는 두 원이 두점에서 ..

https://www.acmicpc.net/problem/10216 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 좌표와 반지름을 입력받아 겹치는 부분은 동일 그룹으로 간주하며 모든 좌표를 입력 받았을 때 몇 개의 그룹이 있는지를 찾는 문제입니다. 우선 이 문제를 풀기 위해서는 겹치는 부분 즉 원이 한점이나 두점에서 만나야 동일 그룹이 될 수 있다는 것을 알 수 있습니다. 즉 두점 사이의 거리가 반지름의 합보다 작거나 같으면 동일 그룹이 될 수 있습니다. 따라서 이러한 그룹들을 찾아내어 인접리스트를 만들었습니다. 즉 어떤 진영의 enemy가 어떤 진영들과 통신이 가능한지를 벡터에 집어넣은 뒤 dfs라는 함수를 만들어 동일 그룹을 탐색하여 그룹의 수를 늘리는 방식으로 문제를 해결 하였습니다..

https://www.acmicpc.net/problem/3933 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 양의 정수는 많아야 4개의 제곱수로 표현 할 수 있다는 라그랑주의 네 제곱수 정리에 따라 어떤 수를 입력 받았을 때 그 숫자가 몇 개의 4개 이하의 제곱수의 합으로 표현 될 수 있는지 구하는 문제입니다. 입력은 2^15보다 작은 숫자가 들어오므로 저는 그냥 for문을 4번 돌려서 해결을 하였습니다. 더하는 과정에서 값이 커질 경우 break를 해주면서 불필요한 횟수를 줄이면 입력이 그렇게 크지 않아서 시간안에 해결이 됩니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with..

https://www.acmicpc.net/problem/14928 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 어떤 수를 20000303 으로 나눈 나머지를 구하는 문제입니다. 문제는 입력 될 수 있는 숫자가 어마어마하게 크므로 정수형 데이터로는 이 숫자를 담을 수가 없습니다. 따라서 큰수를 20000303으로 나누는 나머지를 어떻게 구할지 생각해보면 가장 첫번째 자리부터 20000303으로 나눈후 그 나머지에 10을 곱하고 그수와 두번째 자리 수를 더해서 또 나누고 그것을 20000303으로 나누고 또 그나머지에 10을 곱하고 더하는 방식으로 진행하면 최종적으로 큰수를 20000303으로 나눈 나머지를 얻게 됩니다. 즉 예를 들어 4321을 11로 나눈다면 이 방법은 4000을 1..

https://www.acmicpc.net/problem/1038 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 숫자가 첫번째 자리수부터 순서대로 감소하는 N번째 숫자를 찾는 문제입니다. 1000000번째 숫자까지 입력이 가능하므로 단순히 각 자리수를 차례대로 비교하면서 찾는 방법으로는 시간초과가 나게 됩니다. 그래서 불필요한 탐색을 줄일 수 있는 방법은 더큰 감소하는 수는 작은 감소하는 수에 숫자를 덧붙이면 만들어 진다는 것을 알 수 있습니다. 따라서 큐에 0~9는 기본적으로 감소하는 수이므로 넣어주고 각각 숫자들로 만들 수 있는 감소하는 수를 넣어주고 다 만든 숫자는 pop해주면서 N번째 숫자를 찾았습니다. 다음은 코드입니다. #include #include using namespa..

https://www.acmicpc.net/problem/1937 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 시간 제한이 있기 때문에 일반적으로 모든 좌표에서 생존 가능일을 구하게 되면 시간 초과가 납니다. 제가 아직 dp문제에 익숙하지 않아서 푸는데 고생을 많이 하였습니다 ㅠㅠ.. 기본적으로 mov라는 이동 함수를 만들고 이를 재귀적으로 탐색을 하는데 이 과정에서 이미 갱신이 되어있는 좌표는 보지않고 넘어가도 되는것이 포인트 입니다. 또한 한 좌표에서 여러 방향으로 이동이 가능 할 경우 각 방향으로 들어가서 끝까지 간다음 그때의 생존가능일 들을 비교하여 더큰 값이 남도록 해주면 됩니다. 예시를 들자면 어떤 좌표 x,y에서 5칸이 이동 가능하다면 1 -> 1 -> 1 -> 1-> 1..

https://www.acmicpc.net/problem/9020 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 모든 짝수는 두 소수의 합으로 이루어져 있다는 골드바흐의 추측을 만드는 문제입니다. 소수의 합인 경우가 여러가지 나올 경우 두수의 차이가 가장 작은 경우를 출력하라고 하였습니다. n이라는 숫자가 있다면 이 숫자는 n/2 에서 동일하게 떨어져 있는 두 수의 합으로 나타난 다는 것을 알 수 있습니다. 따라서 n이 짝수이므로 n/2에서 한칸씩 앞 뒤로 움직이며 두 수가 모두 소수가 되는 시점이 또한 두 수의 차가 가장 작은 조건도 만족 한다는 것을 알 수 있습니다. 다음은 코드입니다. #include #include //에라토스테네스의 체 using namespace std; in..