알고리즘23 4105 유클리드 https://www.acmicpc.net/problem/4105 4105번: 유클리드 유클리드는 자신의 공책에 다음과 같은 문제를 풀기 위한 복잡한 과정을 적어놓았다. 하지만, 컴퓨터를 이용하면 쉽게 구할 수 있다. 이차원 평면 위에 선분 AB와 점 C, 삼각형 DEF가 있다. 점 C는 www.acmicpc.net 기하학 문제를 풀 때 연습장을 쓰게 되더라. 그래도 다른 카테고리의 문제들은 애매한 부분이 남아 문제를 완벽히 풀었다는 생각이 잘 들지 않는데, 이런 문제들은 수식으로 정확히 표현되니까 정말 좋다. 접근 일단 삼각형과 평행사변형의 넓이가 같다는 조건을 쓰기 위해 삼각형의 넓이를 구해야 한다. 세 변만 주어졌으므로 헤론의 공식을 통해 삼각형의 넓이를 구해보았다. $$ \triangle DEF .. 2022. 9. 5. 3199 ABCD https://www.acmicpc.net/problem/3199 3199번: ABCD 정찰 부대가 지금 막 새로운 보고를 보내왔습니다. 그 보고의 내용은 바로, ABCD(Atomic Beryllium-Cesium Destroyer)라는, 이름만 들어도 소름이 끼치는 병기가 테러리스트들에게 넘어갔다는 것입니다. ABCD www.acmicpc.net 부품들이 4개의 레일 위를 이동하면서 정확히 직사각형을 만들 때 자폭한다. 폭발력은 직사각형의 넓이다. 최소한 넓이를 줄여야 한다. 기하학다운 문제다. 풀리니 짜릿하다! 접근 직사각형의 성질중에 마주보는 변의 길이가 같다는 점을 생각했다. 만약 A와 B의 길이가 C와 D의 길이와 다르다면 마주보는 변의 길이가 같을까? 정확하게 그리지 못했지만 아무튼 직사각형의.. 2022. 9. 4. 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. 이전 1 2 3 4 다음
