본문 바로가기

전체 글

 (333)
[백준 / BOJ] 1113 수영장 만들기 문제 출처 : www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net N*M크기의 칸에 수영장을 만들려고 한다. 각 칸에 그 땅이 갖고있는 높이가 주어졌을때, 수영장에 물을 얼만큼 넣을수있는지 구하는 문제이다. 만약 수영장이 다음과 같다면, 16661 61116 16661 가운데 3개의칸에 5씩 넣어서 총 15만큼의 물을 넣을수있다. 만약 5보다 더 많이 넣는다면 수영장 벽의 높이인 6보다 커져서 물이 넘친다. 풀이 한달전에 풀었던 문제였다...
[백준 / BOJ] 2206 벽 부수고 이동하기 문제 출처 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N*M행렬이 주어진다. 이때, 이동할수있는곳은 0 벽이있어서 이동할수 없는곳은 1로 표시된다. 이동할때 벽을 최대 1회 부수고 이동할수있는데, 1,1에서 시작해서 N,M에 도달했을때 최단경로를 구하는 문제다. 풀이 BFS문제다. 일반적인 BFS와 check배열을 선언하는게 다른데, 3차원 체크배열을 선언해서 해당 지점에 벽을 부수고 이동한 경로와 최솟값과 벽을 부수지 ..
[백준 / BOJ] 17485 진우의 달 여행 (Large) 문제 출처 : www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 진우가 지구에서 출발해서 달에 도착했을때, 필요한 자금을 최소화 하는문제다. 달에서 지구까지 가는길에 각 칸에 자금이 주어진다. 풀이 N,M이 각각 최대 1000이고, 한 인덱스에서 아래로 갈수있는방향이 3가지 (왼쪽아래 오른쪽아래 중간) 이므로 완전탐색으로 풀려고하면 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 했는데, dp배열을 구현하고 사용하는게 힘..
[백준 / BOJ] 1629 곱셈 문제 출처 : www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net a를 b제곱한 수에 c를 나눈 나머지를 구하는 문제다. 풀이 B의 최댓값이 21억이므로 반복문으로 제곱을 해주면 총 21억번 반복을 하게되어서 시간초과가 난다. 분할정복과 수학공식을 이용해서 시간을 최소화해 구해야하는 문제였다. a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 을 사용한다. 단, 지수가 홀수일때는 a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 * a를 해주는것에 유의해야한다. 이해를 돕기위해 위 그림을 보자. 2^8을 계속해서 공식을 사..
[백준 / BOJ] 2410 2의 멱수의 합 문제 출처 : www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 자연수 N을 입력받았을때, 그 자연수를 2의 멱수의 합으로 나타내는 경우의수를 구하시오 예를들어 3 1 + 1 + 1 1 + 2 두가지 경우로 나타낼수있다. 풀이 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력받은 동전들을 ..
[백준 / BOJ] 1261 알고스팟 문제 출처 : www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net N*M크기의 미로가 주어진다. 미로는 0,1로 주어지며 0은 빈 방 1은 벽이다. 알고스팟 운영진이 (1,1)에서 (N,M)으로 이동할때까지 총 몇개의 벽을 부숴야하는지 구하는 문제이다. 풀이 다익스트라를 이용해서 푸는문제다. 벽을 부순 횟수를 저장하는 배열을 만들고 배열의 모든칸을 최댓값으로 초기화 시켜준다. (나는 1000000000로 초기화 해줬음) 위 배열에는 해당 (..
[백준 / BOJ] 13325 이진트리 문제 출처 : www.acmicpc.net/problem/13325 13325번: 이진 트리 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거�� www.acmicpc.net 1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다. 풀이 (백준에서 1초에 반복문이 1억번 돈다고 들은것같다..) 최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... ..
[백준 / BOJ] 6118 숨바꼭질 문제 출처 : www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

티스토리툴바