맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
#작성 코드
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int n;
int **tri;
int **triSum;
int main(){
// 정수 삼각형의 크기 입력
scanf("%d", &n);
// 정수 삼각형 할당 인덱스 1에서부터 사용. i 층에는 i개만큼 배열 할당
tri = new int*[n+1];
for(int i=1; i<=n+1; i++){
tri[i] = new int[i];
}
// 정수 삼각형의 합을 저장할 이차원 배열 할당.
// triSum[i][j]에는 i층 j번째 원소까지의 합 중 가장 합이 큰 경로의 합 저장
triSum = new int*[n+1];
for(int i=1; i<=n+1; i++){
triSum[i] = new int[i];
}
// 정수 삼각형 입력
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
scanf("%d", &tri[i][j]);
}
}
// 첫 번째 합 = 첫 번째 원소
triSum[1][1] = tri[1][1];
// 두 번째 층부터 시작
for(int i=2; i<=n; i++){
for(int j=1; j<=i; j++){
// 해당 층의 첫 원소일 때
if( j==1 ){
triSum[i][j] = triSum[i-1][j]+tri[i][j];
}
// 해당 층의 마지막 원소일 때
else if( i==j ){
triSum[i][j] = triSum[i-1][j-1]+tri[i][j];
}
// 안쪽에 있는 원소라면 이전 층의 j-1, j번째까지의 triSum 중에서
// 큰 쪽을 선택하여 이번 층의 원소를 더한다.
else{
triSum[i][j] = max(triSum[i-1][j-1], triSum[i-1][j])+tri[i][j];
}
}
}
int result=0;
for(int i=1; i<=n; i++){
result = max(result, triSum[n][i]);
}
printf("%d", result);
return 0;
}
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
#작성 코드
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int N;
int house[1001][3];
int tmp[3]; // 현재까지 선택의 최솟값들 저장.
int choice[3];
int answer(){
tmp[0] = house[1][0]; // 첫번째 집에서 빨강 선택
tmp[1] = house[1][1]; // 첫번째 집에서 초록 선택
tmp[2] = house[1][2]; // 첫번째 집에서 파랑 선택
// 두번째 집부터 마지막 집까지 순회
for(int num=2; num<=N; num++){
// 새 집에서 빨강 선택 <- 이전 집에서 초록, 파랑 선택한 결과 중 작은것
choice[0] = house[num][0]+min(tmp[1], tmp[2]);
// 새 집에서 초록 선택 <- 이전 집에서 빨강, 파랑 선택한 결과 중 작은것
choice[1] = house[num][1]+min(tmp[0], tmp[2]);
// 새 집에서 파랑 선택 <- 이전 집에서 빨강, 초록 선택한 결과 중 작은것
choice[2] = house[num][2]+min(tmp[0], tmp[1]);
// 각 결과들을 재사용할 수 있도록 저장.
tmp[0] = choice[0];
tmp[1] = choice[1];
tmp[2] = choice[2];
}
// 모든 집을 순회한 후, 제일 마지막 집에서 빨강, 초록, 파랑 선택한 누적 결과 중 최솟값 리턴
return min(min(tmp[0], tmp[1]), tmp[2]);
}
int main(){
scanf("%d", &N);
for(int i=1; i<=N; i++){
// 각 집을 빨강, 초록, 파랑으로 칠하는 비용
scanf("%d %d %d", &house[i][0], &house[i][1], &house[i][2]);
}
printf("%d\n", answer());
return 0;
}
##
집의 수 N은 최대 1000, 각 집에 칠할 수 있는 R, G, B 비용 ->int house[1001][3]배열을 선언
#191216 review
아래의 코드처럼 1~i번째 집을 칠하는 비용을 저장하는 배열을 추가 선언하여도 메모리 상에서 크게 차이나지않는다.
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
#작성 코드
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, V;
vector<int> node[1001]; // 정점 최대 1000개
// dfs와 bfs에서 사용할 방문여부 체크 배열
bool visitDfs[1001]={ false, };
queue<int> bfsQ; // bfs결과를 순서대로 저장하기위한 큐
bool visitBfs[1001]={ false, };
void dfs(int v, int cnt){
int x=v;
visitDfs[v] = true;
printf("%d ", x);
// N개 노드 모두 방문했다면 dfs함수 종료
if( cnt==N ){
return;
}
// node[v]에 연결된 노드 중 방문하지 않았던 노드들 반복적으로 방문.
for(vector<int>::iterator i=node[v].begin(); i<node[v].end(); i++){
if( visitDfs[*i]==true ) continue;
dfs(*i, cnt+1);
}
}
void bfs(int v){
// 처음에 방문하는 정점을 큐에 넣는다.
visitBfs[v] = true;
bfsQ.push(v);
// 큐가 빌 때까지 반복
while( !bfsQ.empty()){
int x = bfsQ.front(); // 큐의 front에 있는 정점 정보 저장, 출력하고 pop
printf("%d ", x);
bfsQ.pop();
// 큐의 front에 있던 정점에 연결된 정점들 중 방문하지 않은 정점을 숫자가 작은 순서대로 큐에 저장
for(vector<int>::iterator i=node[x].begin(); i<node[x].end(); i++){
int y = *i;
if( visitBfs[y]==false ){
bfsQ.push(y);
visitBfs[y] = true;
}
}
}
}
int main(){
// 정점개수, 간선개수, 탐색 시작할 정점 번호
scanf("%d %d %d", &N, &M, &V);
for(int i=1; i<=N; i++){
node[i].push_back(i);
}
for(int i=1; i<=M; i++){
int a, b;
scanf("%d %d", &a, &b);
node[a].push_back(b);
node[b].push_back(a);
}
// 각 노드의 연결상태 오름차순으로 정렬(맨 앞: 부모)
for(int i=1; i<=N; i++){
sort(node[i].begin(), node[i].end());
}
dfs(V,0);
printf("\n");
bfs(V);
return 0;
}
##
N : 정점. 최대 1000개 입력 가능 하므로 vector<int> node[1001] 생성. 인덱스 1~1000까지 사용한다.
