본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 20157 화살을 쏘자 문제 출처 : www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풍선들의 (X,Y)가 주어졌을때, 호준이가 화살을 쏠때, (화살은 포물선이 아닌 직선으로 날라감) 한번에 터트릴수 있는 풍선의 최대갯수를 구하는 문제다. 풀이 풍선의 갯수가 10만개이다. 일반적인?? 완전탐색으로 모든경우를 볼경우 O(N^2)이 나와서 시간초과가 뜬다. 완전탐색으로 풀되, 저장을 다르게 해야하는데, 나는 딕셔너리에 {기울기, 해당 기울기의 풍선의 갯수} 로 저장해 주는식으로 ..
[백준 / BOJ] 17911 Keyboards in Concert 문제 출처 : www.acmicpc.net/problem/17911 17911번: Keyboards in Concert The first line of input is two space separated integers; n (1 ≤ n ≤ 1 000) the number of instruments, and m (1 ≤ m ≤ 1 000), the number of notes in the tune. This is followed by n lines, each starting with an integer ki (1 ≤ ki ≤ 1 000), the nu www.acmicpc.net 올라브는 전자키보드를 갖고있다. 이 전자키보드로 노래를 연주하려고 하는데, 키보드가 고장나서 모든 음을 연주할수없다. 한번에 ..
[백준 / BOJ] 19581 두 번째 트리의 지름 문제 출처 : www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리가 주어졌을때 두번째로 긴 트리의 지름을 구하는 문제다. 풀이 트리의 지름을 구하는 임의의 지점에서 가장 먼지점 A를 찾고, A에서 가장 먼 지점 B를 찾으면 된다. 이걸 좀더 응용하면 되는데, 1. 임의의 지점 O 에서 가장 먼지점 A를 찾고, A에서 두번째로 먼 지점 B를 찾는다. 2. 임의의 지점 O 에서 두번째로 먼지점 C를 찾고, C에서 가장 먼 지점 D를 찾는다. 두 값..
[백준 / BOJ] 10164 격자상의 경로 문제 출처 : www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net N*M 그리드에서 무조건 (1,1) 에서 시작하여 (Y,X)지점을 지나 (N,M)지점에 최소한의 이동으로 도달하는 경로의 수를 구하는 문제다. 풀이 dp로 풀리는 문제였다. 전 지점에 최소로 도달하는 경로의 수를 알고있다면, 현재위치까지 오는 경로의 수를 알수있다. 예제처럼 3*5 그리드가 있다고 가정해보자 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0..
[백준 / BOJ] 9518 로마 카톨릭 미사 문제 출처 : www.acmicpc.net/problem/9518 9518번: 로마 카톨릭 미사 로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다. 성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉 www.acmicpc.net 상근이가 교회 미사동안 최대한 많은사람과 악수를 하려고 한다. 악수는 자기 자리에서 8방향으로 할수있으며, (대각선 + 상하좌우) 상근이는 항상 가장 많은사람과 악수를 할수있는 자리에 앉는다고 할때, 미사가 진행되는동안 몇번악수를 할수있는지 구하는 문제다. 풀이 범위가 크지않아서 완전탐색으로 풀리는 문제였다. 주의할점이 "상근이가 악수를 하는 경우" 가 아니라 "모든 사람이 악수를 하는 경우..
[백준 / BOJ] 5427 불 문제 출처 : www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 상근이가 빌딩을 탈출하려고한다. 이때, 벽이있는곳이나 불이 붙은곳으로는 이동할수없다. 불은 1초마다 상하좌우로 번지며 벽으로는 번지지못한다. 상근이는 1초마다 상하좌우로 움직이며, 벽으로 이동하지 못한다. 가장빠르게 빌딩 밖으로 나가는 경우를 찾는 문제다. 풀이 BFS두번으로 풀리는 구현문제였다. 1. 우선, 불의 위치를 전부 저장해놓은다음, 각각의 위치를 기준으로 BFS를 돌린다. 이때 해당(y,x)지점에 ..
[백준 / BOJ] 14595 동방 프로젝트 (Large) 문제 출처 : www.acmicpc.net/problem/14595 14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net 동아리방을 합치는 연산이 여러번 주어졌을때, 이 연산이 모두 끝난후, 남아있는 방의 수를 출력하는 문제다. 풀이 시간초과를 피하기위해 유니온파인드를 이용해서 풀어야한다. 방이 총 5개있을때, 각 방은 이런식으로 떨어져있을것이다. (예제 1) 이때, 1번방과 2번방을 합치는 연산을하면 1번방과 2번방은 같은방이되는데, 그걸 이렇게 연결..
[백준 / BOJ] 14699 관악산 등반 - Swift 문제 출처 : www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net N개의 쉼터가 있고, 쉼터둘을 연결하는 M개의 도로가 있다. 각 쉼터에는 높이가 있으며, 항상 현재쉼터보다 높은위치로만 갈수있다고할때, 각 쉼터에서 최대한으로 방문할수있는 쉼터의 갯수를 구하는 문제다. 풀이 전에 풀었던 Dp+DFS문제인 욕심쟁이 판다 : www.acmicpc.net/problem/1937 와 비슷한 유형?의 문제라고 생각했다 *항상 현재 쉼터 보다 높은 쉼터로만 ..

티스토리툴바