본문 바로가기
반응형

Problem Solving232

[그리디] 백준 2217번: 로프 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 그리디인지 잘 모르겠다. 조금 생각하면 풀이가 보이는 문제! n = int(input()) ropes = [] for i in range(n): ropes.append(int(input())) ropes.sort() tones = [] for i in range(len(ropes)): rope = ropes[i] tones.append(rope*n) n -= 1 print(max(tone.. 2021. 5. 25.
[그리디] 백준 1541번: 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 유형의 문제고, 답을 어떻게 낼지 생각을 해야한다. 괄호를 원하는 만큼 칠 수 있는 상황이라면, 다음이 가능하다. 예를 들어 10+20+30-40+50+60-70-80+90-100가 있을 때 괄호를 적절히 쳐서 최솟값을 만들어보면 다음과 같이 된다. 10+20+30-(40+50+60)-70-(80+90)-100 즉 식을 10+20+30-40-50-60-70-80-90-100으로 만들 .. 2021. 5. 25.
[DFS, BFS] 백준 7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 으아아아악!!! 중간에 꼬여서 3시간 정도 걸린 거 같다.. import collections y_lim, x_lim = map(int, input().split()) table=[] for i in range(x_lim): table.append(input().split()) q = collections.deque() for x in range(x_lim): for y in ra.. 2021. 5. 24.
[DFS, BFS] 백준 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import collections n = int(input()) link = int(input()) table = collections.defaultdict(list) for i in range(link): a, b = map(int, input().split()) table[a].append(b) table[b].append(a) discovered=[] def dfs(computer): for ot.. 2021. 5. 24.
[DFS, BFS] 백준 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 섬을 세는 유명한 문제에 갯수까지 세는 것이 추가된 문제다. DFS로 탐색하면서 미지의 단지를 발견할때 마다 island에 1을 더해주고 ( 단지 개수) 집을 발견할때마다 1을 더해주는 식으로 단지 내 집 개수를 구하였다. n = int(input()) table = [] for i in range(n): table.append(list(input())) island = 0 houses = [] d.. 2021. 5. 24.
[DFS, BFS] 백준 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net x_lim, y_lim = map(int, input().split()) maze = [] for i in range(x_lim): r = input() maze.append(list(r)) q = [[0,0,1]] # x, y, walk while q: cur = q.pop(0) x = cur[0] y = cur[1] walk = cur[2] if x == x_lim-1 and y == y_lim-1: print(walk) b.. 2021. 5. 24.
반응형

티스토리툴바