Problem Solving/BOJ
-
[BOJ] #2644 _ 촌수계산Problem Solving/BOJ 2019. 8. 28. 20:49
[촌수계산] https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 www.acmicpc.net 부모가 한명 뿐이기 때문에 부모만 저장하여 쉽게 풀 수 있다. 부모배열에 부모를 다 저장해두고, 상위로 올라가면서 공통의 부..
-
[BOJ] #2468 _ 안전 영역Problem Solving/BOJ 2019. 8. 28. 20:03
[안전 영역] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net bfs나 dfs를 이용하여 안전한 구역의 개수를 세는 문제이다. [ 소스 코드 ] #include #include #in..
-
[BOJ] #3190 _ 뱀Problem Solving/BOJ 2019. 8. 12. 23:14
[뱀] https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 시뮬레이션 문제이다. 알려준 규칙대로 코드를 구현하면 된다. 이동한 칸에 사과가 없을 경우, 꼬리가 위치한 칸을 비워주는 것이 관건이다...
-
[BOJ] #14889 _ 스타트와 링크Problem Solving/BOJ 2019. 8. 12. 23:08
[스타트와 링크] https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net dfs를 이용하는 문제이다. next_permutation을 이용하면 더 쉽게 구현할 수 있지만, {a, a, a, b, b, b}와 {b, b, b, a, a, a}를 중복 계산한다. (단, 중복 계산해도 시간 초과는 발생하지 않기 때문에 사용해도 된다.) 중복 계산하지 않도록 구현하기 위해 아래와 같이 재귀 함수를 이용하여 구현하였다. [ 소스 코드 ] #include #include #inclu..
-
[BOJ] #9465 _ 스티커Problem Solving/BOJ 2019. 8. 12. 22:34
[스티커] https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 아주 간단한 DP문제이다. 100점인 스티커를 기준으로 가능한 경우는 아래와 같이 3가지다. 이를 이용하여 점화식을 만들 수 있..