import sys sys.stdin = open('input.txt') input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(q): while q: val, node = heappop(q) if dist[node] temp: dist[next_node] = temp heappush(q, [temp, next_node]) N = int(input()) lives = list(map(int, input().split())) lives = s..

백준 18353 - 병사 배치하기 시간 제한 1초, 메모리 제한 256MB # 조건 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 ..

백준 14247 - 나무 자르기 시간 제한 2초, 메모리 제한 512MB # 조건 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 $n$개의 나무가 있는데, 영선이는 하루에 한 나무씩 $n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다. 따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데, 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오. 참고로, 자른 이후에도 나무는 $0$부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다. 입력 첫째 줄에는 나무의 개수 N개가 있다. 나무는 1번부터 ..

백준 5052 - 전화번호 목록 시간 제한 1초, 메모리 제한 256MB # 조건 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번..

백준 10713 - 기차 여행 시간 제한 1초, 메모리 제한 256MB # 조건 JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다. 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다. 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다. JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다. 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다. 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다. 하지만 IC카드로 철도를 탈 때는 IC카드를 미리 구입해둬야만 한다. 철도 i에서 쓸 수 있는 IC카드를 구입하는데..

백준 15684 - 사다리 조작 시간 제한 2초, 메모리 제한 512MB # 조건 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을..

코드트리 - 술래 잡기 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai # 소요 시간 - 70분 # 접근 방법 구현하기 어려웠던 부분은 술래가 움직이는 달팽이 모양의 방향이었다. 정방향과 역방향으로 움직일 때 다음 위치를 미리 나타내줄까 고민하였지만 따로 catcher리스트를 관리하는게 편해보여 정의해주었다. 현재 i, 현재 j, 달팽이 인덱스, 방향, 진행한 칸 수 우선 달팽이 모양으로 움직이는 것을 잘 살펴보면, 현재 위치를 제외하고 1 1 2 2 3 3 4 4 칸씩을 가면서 방향을 회전한다. 조금 더 디테일 하게는 방향을 전환했을 때, 위나 아래..

코드트리 - 나무박멸 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai # 소요시간 : 100분 # 접근 방법 구현, 시뮬레이션 문제로서 의사 코드를 탄탄히 작성하는데 집중하였다. 우선 주어진 조건을 정리하며 아래 키 포인트를 위주로 고민하였다. 나무들이 동시에 움직이며, 나무가 성장한 후 번식을 한다는 점 제초제는 가장 많은 나무가 박멸되는 위치에 뿌리고, 빈 칸을 만나는 경우에도 제초제를 뿌리고 종료하는 것 제초제는 c년만큼 남아있고, 다시 뿌리면 c년으로 초기화된다는 점이다. 제초제를 따로 리스트에 보관하지 않고 주어진 arr에 기록하기 위하여 입..

코드트리 - 꼬리 잡기 # 소요시간 - 100분 # 접근 방법 s 기업 코딩테스트 대비 구현, 시뮬레이션 문제를 풀게 되었다. 문제를 읽으면서 주어진 조건을 요약하고 의사 코드로 작성하면서 눈 여겨본 중요한 키포인트는 아래와 같았다. 사람들을 주어진 경로로 이동시키기 라운드에 따른 공을 던지는 시작점과 방향 공을 맞은 사람의 순서와 뒤집기 따라서, 각 팀의 사람들의 위치를 기록할 team_loc리스트와 머리의 위치를 기록할 team_head 딕셔너리를 사용해주었다. 주어진 배열을 순회하며 1을 만나는 경우 idx를 팀 번호로 사용하여 bfs 함수를 실행시켜 각 팀의 머리 ~ 꼬리 순서로 기록해주었다. 이 때, 3을 만난 경우는 따로 temp에 저장해둔 후 마지막에 추가해주었다. 2 1 3이나 3 1 2와..