MuviSsum

www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 문제: 준석이가 돈을 내고 친구를 구하는데, 친구의 친구도 친구가 된다. 최소비용으로 모든 친구를 사겨라. 요즘 최소 스패닝 트리에 대해 다시 리마인드하는 차에 크루스칼 알고리즘의 부모 격인 유니온 파인드 문제들을 풀어보고 있습니다. 거기서도 대표 문제 격인 "친구비" 문제입니다. 사실 문제 이해하는 단계를 지나 알고리즘 분류를 통해 들어갔기 때문에 이해 단계를 생..

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..

문제 풀다가 어 이거 내가 숏코딩 1위 찍을 수 있겠는데 해서 바로 숏코딩 도전!! python3 언어에서 숏코딩 1등 바로 찍었슴당! 비록 S4의 쉬운 문제지만, 저기에 1등에 한번 올랐다는 것에 만족하는 중 ㅎㅎ 저번에 LCS문제는 시간으로 1등먹어서 기분좋았는데, 여기서는 숏코딩 1등 먹어서 기분 좋아요 ✌✌ 코드: N,i=int(input()),2 while N>1: while N%i:i+=1 print(i);N/=i

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/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 문제 : 주어진 수영장들의 영역(부피)를 구하라. 풀이 : 1. DFS / BFS 둘 다 가능한데, BFS가 좀 더 편하게 풀리는 것 같습니다. 2. 수영장 땅의 최대 높이는 9이니까 1~8까지 높이대로 영역(부피)를 구하여 결과값에 각각 저장해줍니다. 3. 수영장 한 곳을 찝어서 BFS/DFS를 돌릴 때, 수영장 밖으로 나가면 거기는 수영장이 아니고, 그 안에서만 돌면..

백준 문제 주소: www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 : 파이프를 주어진 NxN배열에서 (0,0) -> (N-1,N-1) 까지 옮길 수 있는 방법의 수를 구하라. DP를 사용해서 푸는 문제였습니다. 처음엔 DFS로 풀었다가 14x14 배열까지는 답이 정상적으로 나오는데, 15x15 배열부터는 시간이 오래걸려서 시간초과가 뜹니다. 각 배열에 3차원의 DP를 사용하면 시간을 매우 단축하여 풀 수 있습니다. ※ dpdp(..