본문 바로가기
728x90

전체 글432

[python] 백준 10835 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 해결 사실 처음에 DFS를 이용해서 완전탐색을 하면 쉽게 풀 수 있겠다 싶었다. 하지만 DFS의 시간복잡도는 $O(2^{N})$ 이며 1≤$N$≤2,000이기 때문에 매우 복잡해질 수 있었고 시간초과로 부분점수밖에 얻지 못했다. 사실 숫자가 크고 완전탐색이 필요한 경우는 대부분 DP로 푸는 경우였다. 우선 왼쪽 카드 중 가장 큰 수가 오른쪽 카드 중 가장 큰 수보다.. 2023. 12. 13.
[python] 백준 13335 트럭 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 해결 다리를 que를 이용하여 해결하면 좋겠다는 생각이 바로 든다. que안에 있는 숫자의 합은 l을 넘어서는 안된다. 1초마다 FIFO로 첫 번째 트럭 or 공기(?)가 나가고 대기중인 트럭이 들어오거나 공기가 들어오는 시물레이션을 코딩하면 된다. 공기가 들어갈지 트럭이 들어갈지의 기준은 다리에 있는 무게의 합+대기중인 트럭의 무게가 l보다 .. 2023. 12. 10.
[python] 백준 1069 집으로 https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제 해결 걸을 때 1초에 1만큼 움직인다. 이는 택시기하학으로 움직이는 것이 아니고 자유롭게 대각선이든 반경 1안에 모든 점으로 1초에 이동할 수 있다는 것이다. 점프도 마찬가지다. 일직선으로 할 수 있다는 뜻은 정확히 거리가 D인 지점까지 T초에 간다는 뜻이다. 따라서 현재 거리, 즉 (x,y)와 (0,0) 거리를 구한다. 현재 거리가 한 번에 뛰어서 갈 수 있는 거리보다 크거나 .. 2023. 12. 7.
[C++] 백준 16480 외심과 내심은 사랑입니다. https://www.acmicpc.net/problem/16480 16480번: 외심과 내심은 사랑입니다 수진이는 외심과 내심 없이는 살 수 없다고 말할 정도로 외심과 내심을 사랑한다. 하지만, 갑자기 수진에게 어려운 일이 닥쳤다. 바로 평면에 있는 삼각형 ABC에서 외접원의 반지름의 길이 R이고, www.acmicpc.net 문제 해결 오일러의 삼각형 공식을 알면 풀 수 있고 모르면 풀기 힘든 문제 증명은 중학교 3학년 수준 참고문헌(위키피디아) 오일러 삼각형 정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 오일러 삼각형 정리와 그에 필요한 보조선, 보조점들 기하학에서 오일러 삼각형 정리(Euler三角形定理, 영어: Euler's triangle theorem)는 삼각형의 .. 2023. 12. 6.
728x90