문제 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 문제풀이 1일권, 3일권, 5일권과 그에 따른 쿠폰을 사용해서 리조트 이용을 위한 최소 비용을 구하는 dp 문제이다. bottom-up 방식으로 각각 날에 대해 dp 값을 갱신해주었다. dp[day][coupon]으로 2차원 dp 배열을 선언해서 이용권에 따라 쿠폰 값도 갱신해주었다. 1일권 구매 dp[i+1][j]=min(result+10000 , dp[i+1][j]) 3일권 구매 dp[i+k][j..

문제설명 https://www.acmicpc.net/problem/20923 20923번: 숫자 할리갈리 게임 첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연 www.acmicpc.net 게임의 규칙은 흔히 알고 있는 할리갈리 게임의 규칙과 유사하다. 게임을 m번 반복했을 때 카드를 더 많이 가지고 있는 사람을 출력하는 문제 문제풀이 처음에는 도도와 수연이의 카드 덱과 그라운드 덱을 각각 2개씩 따로 만들어 풀었었는데, if 문의 조건도 복잡해지고 while문을 남발해서 시간초과가 났다 시간초과 문제..

문제 백준 17396 백도어 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 문제풀이 백도어 하는데 걸리는 최단시간을 구하는 문제로 각각의 분기점으로 가는 시간이 가중치가 되는 다익스트라 문제 (n-1)번째 분기점은 값이 1이어도 갈 수 있는 분기점이기에 값이 0인 분기점과 동일 이를 제외한 분기점은 값이 1이라면 continue 해주기 개념정리 다익스트라는 최단경로 탐색 알고리즘으로 시작점으로부터 다른 모든 점까지의..

문제 백준 11582 치킨 TOP N https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 문제풀이 merge sort 의 중간 과정을 출력하는 문제 ; k명이 정렬하는 단계가 완료된 상태 출력 merge 함수를 만들어서 merge sort 진행하기 check 함수를 만들어서 k명 미만이 정렬하면 정렬 중지시키기 코드 import sys input=sys.stdin.readline def check(s,e): if((e..