https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 시도 1 : 실패 -> TC2번과 3번에서 걸리고 있음 from collections import deque N, M, fuel = map(int, input().split()) # fuel = 15 board = [] flag = True customer = [] for _ in range(N): board.append(list(map(int, input(..
Algorithm (PS)
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 교과목 안내와 같이 생긴 이 그래프가 위상정렬 자료구조이다 그런데 그냥 위상정렬이 아니라 건물 건설시간 cost 를 계산해 나가야 한다는 점이 있다 dp[next] = max(dp[now] + times[next], dp[next]) # 누적되는 비용 갱신하기 # 여기서 max 값을 저장해야 하는 이유는 모든 과정이 끝나야 next node로 갈 수 있기 때문이다 ! 따라서 dp 값을 갱신해..
https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net python code 가 잘 안보여서 공유하게 되었다 인덱스 i 번째를 무조건 선택한다고 할 때, i 번째 보다 앞에 있는 그림들 중 선택할 수 있는 가장 높이가 높은 그림을 height 에 저장한다. 그 후, height 에 있는 값을 이용하여 i 번째 그림을 선택할지, 안할지를 max(dp[i-1], dp[height[i]] + array[i][1]) 를 통해 cost 가 큰 쪽을 ..
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 시도 1 : 메모리초과 (PyPy), 시간초과 (Python) import sys sys.setrecursionlimit(10**7) flag = False answer = 0 N = int(input()) a = list(map(int, list(input()))) b = list(map(int, list(input()))) ''' 0 : ON 1 : OFF 직전에 ..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제의 핵심은 옮기는 학생의 최소 수를 구하는 것이고, 옮기는 학생의 최소 수는 전체 배열의 길이 - 가장 긴 증가하는 수열의 길이 와 같다. 가장 긴 증가하는 수열의 길이는 dp 를 이용하여 구할 수 있다. 우선 dp 의 값을 1로 초기화 한다. 그 이유는 '자기 자신' 만 포함하는 길이가 1 인 수열부터 시작하게 되기 때문이다. dp = [1] * (N+1) for i in range(1, N+1):..
https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # https://school.programmers.co.kr/learn/courses/30/lessons/84021 from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def get_position(sx, sy, table, visited, mode): one_piece = [(0, 0)] # 한 조각을 이루는 좌표 리스트 v..
https://www.acmicpc.net/problem/14714 14714번: 홍삼 게임 (Easy) 첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내 www.acmicpc.net 문제 유형을 보면 힌트를 얻을 수 있는데, BFS를 사용하여 풀 수 있는 문제였다.. 방문 처리를 할 때 지목권 a를 가질 사람을 탐색 & 지목권 b를 가질 사람을 탐색 해야 하며 각 turn 마다 지목은 한번만 하므로 이를 3차원 배열로 나타낼 수 있다는 것이 이 문제의 핵심이었다 즉 이를 3차원 배열로 표현하게 되면 visited[지목권 종류][a..
https://www.acmicpc.net/problem/28305 28305번: 세미나 배정 DEVOCEAN은 SK그룹의 대표 개발자 커뮤니티이자, 내/외부 개발자 간 소통과 성장을 위한 플랫폼이다. DEVOCEAN의 콘텐츠로는 SK 개발자들이 직접 작성한 최신 개발 관련 글과 기술을 공유하고, 테크뉴 www.acmicpc.net 위의 문제인데... 참고할 문제로는 강의실 배정, 공유기 설치 문제가 있다. https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net https://www.acmicpc...
