전체 글29 18187 평면 분할 https://www.acmicpc.net/problem/18187 18187번: 평면 분할 무한한 크기의 이차원 평면에, 여러분은 최대 N개의 직선을 그릴 수 있다. 여러분은 기울기가 -1, 0, 1인 직선만 그릴 수 있다. 직선을 이용하여 평면을 최대 몇 개의 영역으로 분할할 수 있는지 구 www.acmicpc.net 접근 문제가 매우 짧아서 마음에 들었다. 기울기가 -1,0,1인 직선만 그릴 수 있다고 제한되어있어서 예시를 그리기 수월했다. 빈 공간을 직선이 가로지르면서 영역을 나누게 되지만, 직선을 교차했을 때도 영역이 나누어진다. 직선을 그릴 때 빈 공간을 가르는 것보다 다른 직선 위를 지나갔을 때 더 많은 영역이 생기기 때문에 최대 개수를 구하기 위해서는 매번 다른 직선 위를 지나갈 선을 그려.. 2022. 9. 3. 4811 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 접근 분명히 이전에 계산한 값을 활용하는게 DP일텐데... 점화식이 어렴풋이 보이는 것 같기도 하고... 문제 이해를 잘 못해 2N일이 지나면 조합의 개수가 2N개인줄 알고 예시를 만들어봐도 안되길래 뭐가 문젠가 싶어 문제를 제대로 읽어보았다. 1. 첫째 날에 알약통에서 온전한 알약 한 조각을 반으로 나눠 하나를 먹고 나머지는 다시 알약통에 넣는다. 2. 둘째 날에 알약통에서 알약 하나를 꺼낸다. 2-1. 온전한.. 2022. 9. 2. 1709 타일 위의 원 https://www.acmicpc.net/problem/1709 1709번: 타일 위의 원 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들이 큰 정사각형을 빈틈없이 채우고 있는데, 정사각형의 한 변의 길이는 짝수이다. 이 한 변의 길이를 Ncm이라고 하자. 큰 정사각형에 www.acmicpc.net 접근 둘레가 그려져 있는 타일의 개수를 구하라는 문제다. 원에 대한 공식이 필요한가 싶었는데 문제 이곳저곳에 힌트가 있었다. N의 범위가 150,000,000이란다. 1번씩 반복을 돌려도 1억 5천만?? 말이 되나 싶어 시간 제한을 봤더니 5초나 주더라. 즉, 하나하나 세어가며 풀어도 된다는 내용같다. 그래도 N*N의 범위를 모두 탐색하는건 아니라고 생각하여 어떤 방법이 가능할까 고민했다... 2022. 9. 2. 16931 겉넓이 구하기 https://www.acmicpc.net/problem/16931 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 생각한 과정 만들어진 정육면체 더미를 한 쪽 면만 보이게 바라보면 어떻게 쌓여있든지 그 쪽 면의 넓이를 간단히 구할 수 있다고 생각했다. 그런데 이 방법은 틀렸다. 이 더미를 짙은 주황색면만 보이도록 바라보았을 때 뒷편에 가려지는 겉넓이가 있다. 단면만 바라보면 안된다는걸 깨닫고, 각 층마다 옆 블록이 인접했는지 따져 겉넓이를 구하기로 했다. 어떤 상황에서든지 윗면과 아랫면은 각각 N.. 2022. 9. 1. 1485 정사각형 https://www.acmicpc.net/problem/1485 1485번: 정사각형 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같 www.acmicpc.net 생각한 과정 정사각형이 되는 조건과 점의 입력순서를 따지느라 매우 애를 먹었다. 점 4개가 주어졌을 때 정사각형이 되는지 안되는지 판단하는 문제다. 처음엔 이렇게 생각했었다. 각 변의 길이가 같고 모든 각의 길이가 90도이니, 변의 길이를 모두 대조하고 변을 벡터로 생각해 내적시켰을 때 0이면 정사각형이 되지 않나? 맞는 말이라고 생각해 그대로 했으나 이유를 모른채 실패했다. 무엇보다.. 2022. 8. 31. 1461 도서관 https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 효율적인 동선을 짜는 문제인데, 들고 다닐 수 있는 책의 개수가 한정되어 있다. 모든 책이 0위치에 있기 때문에 들고 있는 책 정리를 끝냈다면 다시 0으로 돌아와야 한다. 어차피 돌아와야 한다면 책을 정리하러 갔다가 오는 동선에 다른 책들을 정리하면 효율적인 동선이 된다. 따라서 제일 먼 거리를 갔다가 오면서 들고 있는 책들을 정리하게 된다. 책의 위치가 음수일 수도 있으므로 책의 위치를 양수와 음수로.. 2022. 8. 30. 2232 지뢰 https://www.acmicpc.net/problem/2232 2232번: 지뢰 일직선상에 N개의 지뢰가 같은 간격으로 매설되어 있다. 각각의 지뢰는 충격 강도 Pi가 있어서, Pi를 초과하는 힘을 가하면 Pi만큼의 힘을 발휘하며 터지게 된다. 어떤 지뢰가 터지게 되면, 그 지 www.acmicpc.net 문제를 읽어보면 각 지뢰의 충격 강도보다 큰 힘이 전달될 경우 지뢰가 터지면서 그 지뢰의 폭발력(충격 강도와 같은 값)이 양 옆의 지뢰로 전달된다고 한다. 즉, 3 4 5 4 4 로 지뢰가 주어질 경우 3번째 지뢰를 터트리면 1,2,4번째 지뢰는 터지지만 5번째 지뢰는 왼쪽의 지뢰가 가진 폭발력보다 낮은 충격 강도가 아니기 때문에 터지지 않는다. 그러므로, 지뢰가 터지는 경우는 양 옆의 지뢰중 어느.. 2022. 8. 29. 2226 이진수 https://www.acmicpc.net/problem/2226 2226번: 이진수 0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의 www.acmicpc.net 문제에서 말하는 대로 처음 몇 개의 이진수들을 구해보면 아래처럼 나오게 된다. 0 x 1 1 2 01 3 1001 4 01101001 5 1001011001101001 6 01101001100101101001011001101001 7 1001011001101001011010011001011001101001100101101001011001101001 ... dp는 이전에 구했었던 결과를 이용한다.. 2022. 8. 29. 1262 알파벳 다이아몬드 https://www.acmicpc.net/problem/1262 1262번: 알파벳 다이아몬드 알파벳 다이아몬드는 정수 길이의 마름모가 여러 개 누적되는 모양이다. 각각의 마름모는 하나의 알파벳 소문자로 그리며, a로 시작해서 z로 끝난다. (가운데에서부터) 그리고, z 이후에는 다시 a www.acmicpc.net N=5라면 아래의 패턴이 반복될 것이다. ....e........e.... ...ede......ede... ..edcde....edcde.. .edcbcde..edcbcde. edcbabcdeedcbabcde .edcbcde..edcbcde. ..edcde....edcde.. ...ede......ede... ....e........e.... ....e.... ...ede... 9x9크기.. 2022. 8. 20. 9020 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 8=3+5, 20=17+3 ... 이렇게 소수+소수=짝수를 할 수 있다는게 골드바흐의 추측이다. 반대로 생각하면 짝수에서 어느 소수를 빼면 소수가 나오는 경우가 있다는 말이다. 테스트 케이스에 대해서 소수 판별을 해야하므로 소수 리스트를 미리 구해두는게 더 좋겠다. bool isPrime[10001]; void find(){ for(int i=2; i 2022. 8. 19. 이전 1 2 3 다음
