분류 전체보기29 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. 이전 1 2 3 4 5 다음
