프로그래밍/알고리즘23 4105 유클리드 https://www.acmicpc.net/problem/4105 4105번: 유클리드 유클리드는 자신의 공책에 다음과 같은 문제를 풀기 위한 복잡한 과정을 적어놓았다. 하지만, 컴퓨터를 이용하면 쉽게 구할 수 있다. 이차원 평면 위에 선분 AB와 점 C, 삼각형 DEF가 있다. 점 C는 www.acmicpc.net 기하학 문제를 풀 때 연습장을 쓰게 되더라. 그래도 다른 카테고리의 문제들은 애매한 부분이 남아 문제를 완벽히 풀었다는 생각이 잘 들지 않는데, 이런 문제들은 수식으로 정확히 표현되니까 정말 좋다. 접근 일단 삼각형과 평행사변형의 넓이가 같다는 조건을 쓰기 위해 삼각형의 넓이를 구해야 한다. 세 변만 주어졌으므로 헤론의 공식을 통해 삼각형의 넓이를 구해보았다. $$ \triangle DEF .. 2022. 9. 5. 2527 직사각형 https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 접근 평범한 AABB를 구현하라는 문제 같다. 다른 점은 면이 겹쳐지는지, 선이 겹쳐지는지, 점이 겹쳐지는지, 안 만나는지를 출력해야 한다. 일단 만나지 않는 경우는 AABB에 나와있는 대로 하면 된다. 그런데 겹치는 상황에서 면이 겹쳐지는지 선이 겹쳐지는지 점이 겹쳐지는지를 알아야 한다. 사진에 표시한 점들은 직사각형을 나타내는 점들이다. 이 사진은 점이 겹쳐지는 상황을 의미하는데, 잘 보면 빨.. 2022. 9. 3. 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. 이전 1 2 3 4 다음
