Henu
개발냥발
Henu
전체 방문자
오늘
어제
  • 분류 전체보기 (411)
    • DevOps (52)
      • Kubernetes (19)
      • Docker (14)
      • AWS (3)
      • Nginx (4)
      • Linux (4)
      • ArgoCD (1)
      • CN (2)
      • NATS (0)
      • Git (5)
    • Back-End (30)
      • Django (18)
      • Spring (5)
      • JPA (1)
      • MSA (5)
    • CS (87)
      • SystemSoftware (20)
      • OS (25)
      • Computer Architecture (16)
      • Network (23)
      • Database (2)
    • Lang (21)
      • Java (9)
      • Python (4)
      • C# (8)
    • Life (12)
    • 블록체인 (2)
    • Algorithm (204)
      • BOJ (160)
      • 프로그래머스 (19)
      • LeetCode (4)
      • SWEA (1)
      • 알고리즘 문제 해결 전략 (8)
      • DS, algorithms (7)
      • Checkio (5)
    • IT (2)

블로그 메뉴

  • GitHub
  • 글쓰기
  • 관리자

공지사항

  • Free!

인기 글

태그

  • Kubernetes
  • BFS
  • boj
  • 프로그래머스
  • django
  • Network
  • 다이나믹 프로그래밍
  • docker
  • 백트래킹
  • DFS

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Henu

개발냥발

[백준 1328] 고층 빌딩 C++
Algorithm/BOJ

[백준 1328] 고층 빌딩 C++

2021. 6. 7. 00:00
 

1328번: 고층 빌딩

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼

www.acmicpc.net

다이나믹 프로그래밍

 

1. 문제 해결 아이디어

일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데

이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다)

 

일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다.

dp배열을 정해주는 건 어렵지 않았다. 

그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다.

 

그런데 점화식을 도출하기가 정말 어려웠다.

나는 계속 가장 높은 건물의 높이를 움직여가며, 이전 답과 현재 답의 연관성을 찾으려고 했지만 실패했다.

 

힌트 : 높이가 1인 빌딩


N = 3일 때 나올 수 있는 빌딩의 배치는 총 6가지이다.(3!)

(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)

 

여기서 모든 빌딩들의 높이를 1씩 더해주면 어떻게 될까

(2,3,4)(2,4,3)....

 

1씩 더해주어도 답은 그대로 인 것을 알 수 있다.

 

그래서 N = 4인 경우는 높이가 1인 빌딩을 끼워 넣는다고 생각하면 문제가 쉬워진다.!

  • 높이가 1인 빌딩을 가장 왼쪽에 놓을 때 : 왼쪽에서 보이는 빌딩의 수가 1 늘어난다.
  • 높이가 1인 빌딩을 가장 오른쪽에 놓을 때 : 오른쪽에서 보이는 빌딩의 수가 1 늘어난다.
  • 높이가 1인 빌딩을 가장자리가 아닌 곳에 놓을 때 : 왼쪽, 오른쪽에서 보이는 빌딩의 수에 전혀 영향을 미치지 못한다.

빌딩을 가장자리가 아닌 곳에 놓는 경우의 수는 n-2 가 됨을 알 수 있다.

 

위 설명을 점화식으로 나타내면

dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2)

 

높이가 1인 빌딩을 사용하는 생각을 하는 게 정말 어려웠던 문제이다.

IQ 테스트 같기도 하다.. 

 

DP는 다른 알고리즘 유형보다 몇 배는 더 많은 시간이 필요한 유형이라고 생각된다. 

구현보다는 사고력을 요구하는 문제가 많은 것 같아서 정말 길게 보고 공부해야겠다.


2. 코드

bottom up 방식이다

매우 간단하다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
#define MOD 1000000007
using namespace std;
 
int N, L, R;
long long dp[101][101][101];
 
void solve(){
    dp[1][1][1] = 1;
    
    for(int n = 2; n <= N; n++){
        for(int l = 1; l <= N; l++){
            for(int r = 1; r <= N; r++){
                dp[n][l][r] = (dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2)) % MOD;
            }
        }
    }
    cout << dp[N][L][R];
}
 
int main(){
    cin >> N >> L >> R;
    solve();
    return 0;
}
 
Colored by Color Scripter
cs

'Algorithm > BOJ' 카테고리의 다른 글

[백준 8980] 택배 C++  (0) 2021.06.09
[백준 1167] 트리의 지름 C++  (0) 2021.06.07
[백준 4811] 알약 C++  (0) 2021.06.06
[백준 2240] 자두나무 C++  (0) 2021.06.06
[백준 14442] 벽 부수고 이동하기2 C++  (2) 2021.06.06
    'Algorithm/BOJ' 카테고리의 다른 글
    • [백준 8980] 택배 C++
    • [백준 1167] 트리의 지름 C++
    • [백준 4811] 알약 C++
    • [백준 2240] 자두나무 C++

    티스토리툴바