본문 바로가기

DP

[BOJ_Gold 2] - 2611 자동차 경주 [python]
PS/BOJ (Baekjoon Online Judge) 2022. 4. 6. [BOJ_Gold 2] - 2611 자동차 경주 [python] 문제 자동차 경주로는 의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다. 자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다. 각 도로에는 의 예와 같이 그 도로를 지날 때 얻는 점수가 있다. 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점..
PS/BOJ (Baekjoon Online Judge) 2022. 3. 31. [BOJ_Silver 5] - 9655 돌 게임 [python] 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 게임 이론과 동적 계획법을 이용한 웰 노운 문제입니다. 각 플레이어별로 턴마다 1개 or 3개의 돌을 제거하는 경우의 수에 대해 탐색을 진행하며, $DP[x][0-1]$ 을 0 : 상근이의 턴 / 1 : 창영이의 턴이라고 할 때, 해당 플..
PS/BOJ (Baekjoon Online Judge) 2022. 3. 24. [BOJ_Gold 5] 2688 - 줄어들지 않아 [python] 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1
PS/BOJ (Baekjoon Online Judge) 2022. 3. 23. [BOJ_Silver 4] 17626 - Four Squares [python] 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 6..
PS/BOJ (Baekjoon Online Judge) 2022. 3. 23. [BOJ_Silver 5] 9625- BABBA [python] 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까? 입력 첫째 줄에 K (1 ≤ K ≤..
PS/BOJ (Baekjoon Online Judge) 2022. 3. 20. [BOJ_Platinum 2] 12995 - 트리나라 [python] 12995번: 트리나라 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연 www.acmicpc.net 문제 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연결되어 있기 때문에, 임의의 두 도시 사이를 항상 오갈 수 있다. 스타트링크의 직원 K명은 트리나라로 이사를 가려고 한다. 모든 직원은 서로 다른 도시로 이사를 가야한다. 즉, 이사할 도시 K개를 선택해야 한다. 이사할 도시에는 중요한 조건이 하나 있는데, 모든 ..
[BOJ_Gold 3] 2533 - 사회망 서비스(SNS) [python]
PS/BOJ (Baekjoon Online Judge) 2022. 3. 13. [BOJ_Gold 3] 2533 - 사회망 서비스(SNS) [python] 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서..
728x90

티스토리툴바