본문 바로가기

프로그래밍/알고리즘23

6600 원의 둘레 https://www.acmicpc.net/problem/6600 6600번: 원의 둘레 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 실수 x1, y1, x2, y2, x3, y3이 주어진다. 세 점으로 만들 수 있는 원의 지름은 백만을 넘지 않는다. www.acmicpc.net 접근 처음 문제를 보았을 땐 세 점 중 두 점은 원의 지름을 의미하는게 아닌가하는 생각이 들어 각 점의 길이를 구한 후 제일 긴 길이에 2를 곱했었다. 물론 잘못된 접근이다. 이 사진이 적절한 반례가 된다. 결국은 세 점으로 만들어진 삼각형의 외접원을 만들고 그 둘레를 구하는 것이 문제다. 외접원을 만들기 위해 원의 공식을 변형시켜 연립방정식을 조립한 후 해를 구하는 방법이 있지.. 2022. 9. 23.
1500 최대 곱 https://www.acmicpc.net/problem/1500 1500번: 최대 곱 세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다. 만약 S=10, K=3이면, 3,3,4는 www.acmicpc.net 접근 솔직하게, 이 문제는 힌트를 보고 풀었다. 힌트를 보고 나니, 이해하지 못했던 내용이었다. 고등학교에서 배운 산술기하평균에 대해서 이해하지 못했었는데 이 문제를 풀면서 조금은 이해하게 되었다. 미흡했던 점 산술 기하 평균이란, 아래 블로그에서 읽는게 더 정확하고 깔끔한 설명이 될 것 같다. https://m.blog.naver.com/alwaysneoi/10015666876.. 2022. 9. 20.
1059 좋은 구간 https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 접근 설명이 다소 난해하다... N을 포함하는 범위를 만들되, 그 범위 안에 집합의 원소가 속하면 안된다. 만약 N이 집합의 원소로 존재하면 어떻게 해서든지 문제의 조건을 만족할 수 없어서 0을 출력한다. 예를 들어 N을 5라고 하고 집합 S의 원소들을 {3, 1, 10, 8}이라고 할 때 집합의 원소들을 포함하지 않으면서 N을 포함하는 범위를 만들면 [4, 5], [4, 6], [4, 7], [5, 6], [5, 7]이 된다. 그러려면 N보다 작은 집합의 원소들 중 제일 큰 값(A)과 N보다 큰 집합의 원.. 2022. 9. 18.
9465 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 접근 RGB문제와 유사한 문제여서 매우 쉽게 풀었다. 스티커를 떼면 상하좌우에 있는 스티커들은 쓸 수가 없다. 최대한 많은 가치의 스티커를 떼어보자는 거다. 왼쪽부터 스티커를 뜯는다고 생각하자. 직전에 어떻게 뜯었냐에 따라 다음 스티커의 운명이 정해진다. 직전에 아래쪽 스티커를 떼어냈다면 다음 열의 아래쪽 스티커는 뜯을 수 없다. 따라서, 윗쪽 스티커를 떼어내기 또는 스티커를 떼지 않는.. 2022. 9. 10.
2502 떡 먹는 호랑이 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 사실 골드 문제를 풀다가 현타가 와서 실버 문제를 찾게 되었다... 열심히 해야겠다. 접근 호랑이에게 떡을 주는 방법은 어제 준 떡 갯수 + 그저께 준 떡 갯수이다. 피보나치와 똑같은데 문제는 첫 날과 둘째 날에 떡을 몇 개 줬는지 모르고, D번째 날에 K개 만큼 줬다고 한다. 어떤 공식으로 한 번에 풀리지 않을 것 같아 예시를 써보기로 했다. 첫 날에 준 떡 갯수를 //[a]//, 둘째.. 2022. 9. 7.
1876 튕기는 볼링공 https://www.acmicpc.net/problem/1876 1876번: 튕기는 볼링공 첫째 줄에 테스트 케이스의 개수 N이 주어진다. 다음 N개 줄에는 볼링공과 핀 사이의 거리 T (16.0 ≤ T ≤ 18.0)와 공을 던진 각도 X (중심을 기준으로 계산, 10 ≤ X ≤ 80)가 주어진다. www.acmicpc.net 여러 가지 실수를 했기 때문에 조금 아쉬웠다. 문제 자체는 쉬운 편이었으나 삼각함수를 활용하다가 실수를 해서 자꾸 틀렸다. 접근 볼링공을 굴렸을 때 범퍼에 부딪치면 입사각과 같은 각도로 튕겨진다. 범퍼가 아래에만 있는게 아니라 위에도 있으므로 양 옆 범퍼를 모두 부딪치면서 전진하게 된다. 문제를 푸는 방법은 볼링공을 움직이면서 볼링공과 핀의 거리를 구했을 때 둘의 반지름을 합한 .. 2022. 9. 6.

티스토리툴바