Code/BOJ
-
#17406 배열 돌리기 4Code/BOJ 2020. 1. 5. 20:38
출처:https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 회전 연산의 개수가 k 개 주어지고 모두 한번씩 사용돼야 한다. dfs를 통해 어떤 회전 연산을 적용시킬 지 순서를 정해..
-
#2718 타일 채우기Code/BOJ 2020. 1. 5. 20:31
출처:https://www.acmicpc.net/problem/2718 2718번: 타일 채우기 문제 4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다. N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다. N제한은 딱히 www.acmicpc.net 다음 열에서 타일이 놓여져 있을 경우는 다음 그림과 같이 0,1,2,3,4 번 상황으로 표현할 수 있다. 그것이 현재상황이라고 할..
-
#5373 큐빙Code/BOJ 2020. 1. 5. 20:19
출처:https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 세로 12 가로 9 인 cube 배열을 만들어서 명령에 맞는 동작을 하는 단순 구현 문제이다. 고정된 배열을 기준으로 회전을 적용시키는..
-
#17836 공주님을 구해라!Code/BOJ 2020. 1. 5. 20:07
출처:https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출 www.acmicpc.net bfs를 통해 구현하였다. 검을 가지고 있지 않을 경우 벽을 통과할 수 없지만 검을 가진 후부터 벽도 통과할 수 있다...
-
#9328 열쇠Code/BOJ 2020. 1. 5. 10:53
출처:https://www.acmicpc.net/problem/9328 9328번: 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 www.acmicpc.net 각각의 문(영대문자)마다 맞는 열쇠(영소문자)가 있고 열쇠 획득시 같은 알파벳의 문은 몇개가 되든 계속 열 수 있다. 외부에서 침입하여..
-
#17244 아맞다우산Code/BOJ 2020. 1. 3. 12:59
출처:https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 www.acmicpc.net 위 그림과 같이 입력값이 주어져 S에서 출발하여 물건X를 모두 수집하고 E로 도착하기 위한 최단 경로를 구하는 문제이다. 비트..
-
#2096 내려가기Code/BOJ 2020. 1. 2. 19:45
출처:https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 별모양이 3개의 칸 중 하나를 선택하며 밑으로 계속 내려가면서 거쳐간 경로의 최솟값 최댓값을 구하는 문제이다. dp를 이용한 점화식을 구하여 해결하는 문제인데 처음에 dp의 배열을 dp[100001][3]과 같이 지정을 하면서 메모리의 초과가 일어났다. 하지만 dp를 dp[3]으로 지정하고 입력값만을 통해서도 계속해서 dp값을 갱신하면서 마지막 최댓값 최솟값을 구할 수 있다. 점화식 알고리즘은 다음과 같다..