본문 바로가기

728x90

다이나믹 프로그래밍6

[Baekjoon] 1010.다리 놓기/Python - Silver5 ❓문제https://www.acmicpc.net/problem/1010성능 요약코드1 ➡️ 언어:PyPy3, 메모리: 109240 KB, 시간: 96 ms코드2 ➡️ 언어:PyPy3, 메모리: 109240 KB, 시간: 96 ms코드1 ➡️ 언어:Python3, 메모리: 31120 KB, 시간: 32 ms 코드2 ➡️ 언어:Python3, 메모리: 31120 KB, 시간: 32 ms 문제 설명재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 .. 2024. 12. 6.

[프로그래머스] N으로 표현/Python - Lv.3 ❓문제https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr성능 요약메모리: 11 MB, 시간: 19.30 ms 문제 설명아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을.. 2024. 11. 26.

[Baekjoon] 2565.전깃줄/Python - Gold5 ❓문제https://www.acmicpc.net/problem/2565성능 요약메모리: 109240 KB, 시간: 92 ms문제 설명두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위.. 2024. 11. 5.

[Baekjoon] 13305.주유소/Python - Silver3 ❓문제https://www.acmicpc.net/problem/13305 성능 요약 메모리: 46228 KB, 시간: 112 ms 문제 설명 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격.. 2024. 11. 1.

[소프티어] 징검다리/Python - Lv.3 ❓문제https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai언어별 시간/메모리언어시간메모리JavaScript2초256MBC1초256MBC++1초256MBJava2초256MBPython2초256MB이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.서쪽에서 동쪽으로 갈 때 밟을 수 있는 돌의 최대 개수는?제약조건1 ≤ N ≤ 3×10³ 인 정수1 ≤ Ai ≤ 10⁸ 인 정수✍🏻풀이DP문제 기본적으로 모든 돌은 1번 밟을 수 있으므로 1로 초기화한다.높이가 각 3, 2, 1, 4, 5 를 가진 5개의 돌이 주어졌을 때,(3, 4, 5), (2, 4, 5), (1.. 2024. 10. 30.

[Baekjoon] 9461.파도반 수열/Java - Silver3 ❓문제https://www.acmicpc.net/problem/9461성능 요약메모리: 14232 KB, 시간: 100 ms분류다이나믹 프로그래밍, 수학문제 설명오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.✍🏻풀이첫 삼각형은 변의 길이가 1인 정삼각형. 정삼각형을 계속 추가. 3.. 2024. 10. 15.

이전 1 다음

728x90

티스토리툴바