본문 바로가기

분류 전체보기

 (386)
[boj] 백준 2225 합분해 (c++) - dp [문제] https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] (N-L) + L = N 이라고 생각해 볼 수 있다. 이전까지의 숫자 합에 N이 되게 하는 임의의 값 L을 더한 것이 되며, 이때 숫자합은 임의의 값을 제외한 K-1개의 숫자이다. 즉, dp[k][n]가 n을 k개의 숫자로 만들 수 있는 경우의 수라고 하면, 점화식은 다음과 같다. dp[k][n] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][n-2] + dp[k-1][n-1] + dp[k-1][n] [코드] #include #include #includ..
[boj] 백준 5014 스타트링크 (c++) - BFS [문제] https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [풀이] 수식을 이용할 수도 있지만 BFS를 이용한 풀이도 가능하다. [코드] #include #include #include #include #include #define INF 987654321 using namespace std; int f, s, g, u, d; int visited[1000001] = {0, }; void bfs(){ queue q; visited[s] = true; q.pu..
[boj] 백준 14890 경사로 (c++) - 구현 [문제] https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 복잡하게 구현을 하다가 숏코딩 버전을 보게 되어서 해당 코드로 이해하려고 노력했다. 일단 행과 열을 모두 체크해야 하는데, for 문을 두번 돌릴 수도 있으나 같은 배열에 transpose 배열까지 저장해서 한 번에 처리하고 있다. 이 문제에서 고려해야 하는 부분은 낮은 길->높은 길, 높은 길->낮은 길에 경사로를 놓을 수 있느냐이다. 이는 연속된 타일이 L 이상인지를 체크함으로써 알 수 있다. 따라..
[boj] 백준 1238 파티 (c++) - 다익스트라 [문제] https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net [풀이] 구해야하는 것은 2가지이다. 모든 정점에서 x까지의 최단 거리와 x에서 모든 정점까지의 최단 거리. 이 두가지의 합의 최댓값이 답이 된다. 따라서 n개의 모든 노드에 대해서 다익스트라를 돌려 x까지의 최단거리를 구하고, x에서 출발하는 다익스트라를 한 번 돌려서 더하면 된다. 이때, 모든 노드에 대해 다익스트라를 돌리는 것은 (모든 노드) -> x ..
[boj] 백준 2447 별 찍기 10 (c++) - 재귀 [문제] https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net [풀이] n x n 사각형에 대해 가운데 부분이 공백으로 이루어지는 형태가 반복된다는 것을 알 수 있다. 따라서 이 때 어떤 좌표값이 공백이 되는지를 일반화해야 한다. n이 3이면, (1, 1), (1, 4), (1, 7), (4, 1), (4, 4), (4, 7) 등의 좌표가 공백이 된다. → ( i / 1 ) % 3 == 1 && ( j / 1 ) % 3 =..
[boj] 백준 2096 내려가기 (c++) - dp [문제] 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 [풀이] 동적 프로그래밍 문제. 메모리 제한으로 전부 저장해두지 못하기 때문에 input을 입력받은 즉시 비교해서 최대, 최소값을 저장한다. [코드] #include #include #include #include using namespace std; int n; int input[3]; int min_dp[3]; int max_dp[3]; int main() { ios::sync_with_stdio(..
[boj] 백준 5430 AC (c++) - deque [문제] https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [풀이] deque을 이용. reverse boolean 값을 선언해두고 배열이 뒤집어진 상태인지를 반영한 후, 'D'에 대해 뒤집어진 상태이면 deq.pop_back() 함수를, 뒤집어지지 않은 상태이면 deq.pop_front() 함수를 사용한다. 마찬가지로 출력 시에도 배열이 뒤집어진지 확인한 후 deque의 앞 혹은 뒤에서부터 출력해준다. [코드] #include #include #include #include using namespac..
[boj] 백준 11403 경로 찾기 (c++) - 플로이드 워셜 [문제] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 그래프에 있는 모든 정점 (i,j)에 대해 다른 정점으로 가는 경로가 있는지를 구해야 하므로 플로이드-워셜 알고리즘을 이용. [코드] #include #include #include #include #include #include #define INF 987654321 using namespace std; int N; int adj[101][101]; int main() { ios::sync_with_stdio(false..

티스토리툴바