Meme's IT

백준 14658번 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 브루트포스, 라고는 나와있는데 구글링 했을 때랑 다르게 풀었음 K의 갯수가 100개 이하이므로 K기준으로 진행 12 10 4 7 2 4 7 3 3 1 5 6 4 7 12 10 8 6 해당 예제에서 별의 위치를 받고, 얘네를 우선 x기준으로 정렬을 해준다. [(2, 4), (3, 1), (4, 7), (5, 6), (7, 3), (8, 6), (12, 10)] 이런식으로 ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이름이 젤다길래 풀어봤는데 젤다는 안나오고 뭔 강도가... 문제 젤다가 (0, 0)의 위치에서 (N - 1, N - 1) 위치로 이동하는데 맵에는 강도가 있어서 강도가 있는 위치로 지나가면 일정 금액을 뜯긴다.... 그래서 최대한 덜 뜯기고 갔을 때, 잃은 돈을 출력해주기 풀이 다익스트라의 정석같은 문제였음.. 맵과 같은 크기의 리스트를 만든 후, 엄청 큰 값(inf)을 넣어둠 ..

# BFS https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 문제 개구리가 징검다리를 건너는데, 다리에는 각각 숫자가 써져있음 그 숫자의 배수만큼은 그냥 갈 수 있다. 출발지와 목적지가 주어졌을 때, 목적지까지 가는데 얼마나 걸리는지 구하기 ▶ 내가 지금 밟은 칸이 1이 되면 다 갈 수 있음 → 시간 무조건 1 ▶ 배수 만큼은 갈 수 있다고 했으니까 뒤로도 가능함 BFS방식으로 풀었다 풀이 from collections import ..

# Union-Find #DFS 문제 창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다. 두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수도 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 모두 묶어서 하나의 무리라고 한다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라. 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는 두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다. 이후 M개의 줄에 걸쳐서 서로를 알고 있는 두..

문제 Ugly Number란 소인수분해 했을 때, 2 / 3 / 5 로만 이루어진 수를 의미한다. 예외로 숫자 1은 첫번째 Ugly Number로 정의한다. Ugly Number를 순서대로 나열하면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, .... 이때, 숫자 K를 입력받으면, 'K번째' Ugly Number를 출력하시오. 첫줄에는 문제의 개수 Q(1