MuviSsum

www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제: 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라. 문제 이해하기!! 각 보석의 무게와 가격이 있고, 보석 넣을 가방에는 보석 한 개씩 밖에 못 넣으며, 무게 한도가 있다. 위의 조건에서 생각해 볼 것! 냅색 알고리즘인가? - 하지만 가방이 여러개고 가방에는 보석을 하나만 넣는다. 그러므로 냅색 알고리즘 X 그러면 이제 생각해 볼것은 그리디 알..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제: 목표 도시로 이동하는 최소비용을 구하여라. 문제 이해하기!! 최소 비용 그래프문제라면 제일 먼저 생각해봐야 할 것! 바로 다익스트라입니다. 이 문제도 다익스트라인데요. 그래프 연결은 상호적 연결이 아니기 때문에 한 쪽만 연결해 줍니다. 그리고 다익스트라로 비용 구하시면 됩니다. 문제 풀어보기!! 일단 문제를 보면 M이 10만까지 가능하기 때문에 input을 stdin.r..

www.acmicpc.net/problem/19621 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 문제: 회의실에 최대한 많은 사람들이 회의할 수 있도록 만들어라. 문제 이해하기!! 일반 회의실 배정 문제와 다른 문제였습니다. 각 회의마다 인원이 다르고 앞과 뒤의 회의랑 회의시간이 무조건 겹치기 때문에 브루트포스 방법을 쓰는 문제였습니다. 문제에서 시작시간이 순서대로 입력이 들어온다는 말이 없어서 sort()를 해주고 시작했습니다. dfs를 재귀적으로 썼고 종료 조건은 N보다 n이 커지면서 res보다 ..

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제: 캐슬디펜스에서 궁수가 얼마나 많은 적을 죽일 수 있는가? 문제 이해하기!! 한 바둑판에 병사들 여러개 놓고 1초 지날 때마다 한칸씩 전진하는데 마지막 칸의 밖의 칸에서 궁수가 대기타고 있고 그 대기타는 궁수의 범위안에 적이 들어오면 궁수는 쏴 죽입니다. 근데 궁수도 1초에 한 번씩 밖에 못 죽여서 모두를 죽일 수 없는 경우가 생깁니다. 그 때문에 이 문제가 생겼습니다. 즉, 궁수가 있는 칸까지 병사들이 온다면 그 ..

처음에는 하.. 이걸 어떻게 풀어야 하나 생각했는데 보니까 N이 10개더라구요. 그래서 바로 브루트포스로 돌렸습니다!! ㅎㅎ 그러다가.. dfs로 돌리고 페일.. ㅠㅠ 그리고 bfs로 바꿔서 성공했습니다. (나중에 알았지만, dfs도 풀 수 있는데 하... 제가 다 만들어 놓은 코드에서 합계 계산을 잘 못 했더라구요 ㅠㅠ 까빙..) 풀이 방법은 각각의 N-a와 a개의 도시 조합을 나누어서 브루트포스를 돌리면 됩니다. dfs / bfs 방법 둘 다 가능한데, bfs가 쉽습니다... ㅎㅎ bfs 추천 드릴게요! 코드: from itertools import combinations def bfs_com(x, cnt): global res1 Q = connect.get(x)[:] while Q: tmpp = Q..

www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 문제: 민식이가 S 도시부터 E 도시까지 가서 벌 수 있는 돈의 최댓값을 구하여라. 민식이의 고민보다 더 고통스러운 고민이었던 것 같습니다..ㅠ 문제를 풀면서 16~17퍼에서 자꾸 WA가 떠서 정말 힘들었던 문제에요. 최종적으로 찾아낸 반례는 4 0 3 4 0 1 0 0 3 5 1 2 0 2 1 0 0 5 5 10 답: 5 입니다. 타임머신이나 웜홀에서 썻던 코드를 들고와서 재사용했던게 문제가 되네요. 밑을 ..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 : 최장 공통 부분 수열을 찾아라. ⊙ DP - 다이나믹 프로그래밍 제가 백준에서 코드 1등을 했습니다!! 감격쓰~~ ㅎㅎㅎ 감격을 뒤로 하고! 풀이 방법은 DP를 설정하고, DP에 한 배열에서 최장 공통 수열이 되는 대로 찾는 겁니다. 첫 번째 배열의 인덱스 처음부터 끝까지 하나씩을 순서대로 골라, 두 번째 배열 전체를 탐색하면서 둘이 같은지를 비교합니다. 그..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 : 배낭 안에 들어갈 수 있는 최대 가치는? ⊙ DP - 다이나믹 프로그래밍 DP의 기본 문제 중 하나라고 할 수 있는 배낭 알고리즘입니다. 배낭 알고리즘은 계속해서 넣어야 하기 때문에 2차원 DP 배열이 필요하지만, 저는 그냥 배열을 2개 만들어서 참조형식으로 swap하는 형식을 택했습니다. DP가 움직이기 위해서는 전 단계의 DP 배열이..

백준 문제 주소: www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 문제 : 전깃줄이 겹치지 않게 하는 최대 갯수는? ⊙ 최장 증가 수열 ⊙ 메모이제이션(다이나믹 프로그래밍 - DP) ⊙ 이분탐색 메모이제이션과 다이나믹 프로그래밍의 차이점을 잘 모르겠다.. 이거도 공부해봐야지! 아무튼 저 위의 3개를 딱 써서 하면 풀리는 문제이다. 코드 : import sys, bisect N = int(input()) arr = [0] + list(map(in..

백준 문제 주소: www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 테스트 케이스 / 반례 48 40 1666116661166611666116661166611666116661 6111661116611166111661116611166111661116 1666116661166611666116661166611666116661 1666116661166611666116661166611666116661 6111661116611166111661116..