이 영역을 누르면 첫 페이지로 이동
hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

페이지 맨 위로 올라가기

hoonDEV

BOJ 1010 - 다리 놓기 문제풀이

  • 2020.03.19 13:56
  • 알고리즘/문제풀이

문제를 읽고 이해하기

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

 

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라. N, M (0 < N ≤ M < 30)

 

재정의와 추상화

사실 수학적으로만 생각한다면 매우 빠르게 끝낼 수 있는 문제이다. 동쪽이 항상 서쪽보다 원소가 많고, 서쪽의 도시가 동쪽의 도시에 대응되는 방식이 '겹치지 않게'라는 것을 보아, 대응 방식이 하나이다. 이 때, 동쪽의 도시 M개 중 서쪽의 도시 N개를 조합의 수로 선택해주기만 하면 답이 나온다.

 

즉, 답은 C(M, N) = C(M - 1, N) + C(M - 1, N - 1) 이다.

 

이렇게 수학적으로 먼저 생각했어야 했는데, 문제를 곧이곧대로 받아들이는 바람에 이상한 방법으로 알고리즘을 짰다.

아래는 내가 처음 '이상하게' 짠 알고리즘이다.

 

---

서쪽의 첫 번째 도시는 동쪽의 마지막 3개를 제외한 모든 도시를 선택할 수 있다. 그 이유는 마지막 3개를 남겨두지 않을 경우 서쪽의 나머지 3개의 도시는 갈 곳이 없기 때문이다.

 

그래서 서쪽의 첫 번째 도시가 갈 수 있는 범위는 0 ~ M - (N - 1) - 현재 도시 번호(0부터 시작)까지다. 다음 재귀호출을 할 때는 서쪽의 첫 번째 도시가 선택한 동쪽의 도시의 인덱스를 전달해주고, 그 인덱스를 이용하여 서쪽의 두 번쨰 도시가 갈 수 있는 범위를 동쪽의 도시의 인덱스 + 1 ~ M - (N - 1) - 현재 도시 번호까지로 한다.

 

이렇게 반복하다가 서쪽의 모든 도시가 동쪽의 도시와 짝지어졌을 경우 호출을 종료한다.

---

 

코드 작성

// 이상하게 짠 코드...

#include <iostream>
using namespace std;

int arr[30][30];
int ct = 0;

int dp(int count, int n, int m, int start) {
    // 기저
    if (count == n) return 1;

    // 메모이제이션 확인
    int &ref = arr[count][m - start];
    if (ref > 0)
        return ref;

    // 계산
    int sum = 0;
    for (int i = start; i < m - (n - 1 - count); i++)
        sum += dp(count + 1, n, m, i + 1);

    ref = sum;
    return ref;
}

int main() {
    int t, n, m;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= m; k++)
                arr[i][k] = 0;
        }
        cout << dp(0, n, m, 0) << '\n';
    }
    return 0;
}

// 이게 원래..

#include <iostream>
using namespace std;

int cache[30][30] = { 0, };

int dp(int n, int r) {
    // 기저
    if (r == 0 || n == r) // C(n, r) = 1 (n == r or r == 0)이라는 성질 이용
        return 1;
    // 메모이제이션 확인
    int& ref = cache[n][r];
    if (ref > 0)
        return ref;
    // x -> 계산
    ref = dp(n - 1, r) + dp(n - 1, r - 1);
    return ref;
}

int main() {
    int t;
    int n, m;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        cout << dp(m, n) << '\n';
    }
    return 0;
}

 

회고하기

항상 DP 문제를 풀 때마다 수학적으로 생각하지 않고 무턱대고 문제를 곧이곧대로 받아들여 엉뚱한 방향으로 가는 경우가 많다. 이 부분은 종만북에서 얘기하는 재정의와 추상화 과정을 충실히 이행하지 않은 것으로 보인다. 앞으로 DP 문제를 많이 풀어나가면서 개선해나가자.

'알고리즘 > 문제풀이' 카테고리의 다른 글

BOJ 1427 - 소트인사이드 문제풀이  (0) 2020.03.25
BOJ 1181 - 단어 정렬 문제풀이  (0) 2020.03.25
BOJ 1026 - 보물 문제풀이  (0) 2020.03.25
BOJ 11286 - 절댓값 힙 문제풀이  (0) 2020.03.19
BOJ 2630 - 색종이 만들기 문제풀이  (0) 2020.03.18

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • BOJ 1181 - 단어 정렬 문제풀이

    BOJ 1181 - 단어 정렬 문제풀이

    2020.03.25
  • BOJ 1026 - 보물 문제풀이

    BOJ 1026 - 보물 문제풀이

    2020.03.25
  • BOJ 11286 - 절댓값 힙 문제풀이

    BOJ 11286 - 절댓값 힙 문제풀이

    2020.03.19
  • BOJ 2630 - 색종이 만들기 문제풀이

    BOJ 2630 - 색종이 만들기 문제풀이

    2020.03.18
다른 글 더 둘러보기

정보

hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

  • hoonDEV의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그

카테고리

  • 분류 전체보기 (91)
    • 일상 (13)
      • 후기 (1)
      • 계획 (11)
    • 공지사항 (1)
    • 알고리즘 (54)
      • 문제풀이 (53)
      • 이론 (1)
    • 공부 (19)
      • React (0)
      • Angular (5)
      • Java (3)
      • C, C++ (3)
      • JavaScript (6)
      • WEB (2)
    • 디자인 (1)
      • UI, UX (1)
    • 개발 (0)
      • boom (0)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • es6
  • 이분탐색
  • 알고리즘
  • dp
  • 그리디
  • 백준
  • 문제풀이
  • javascript

나의 외부 링크

정보

훈개발자의 hoonDEV

hoonDEV

훈개발자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 훈개발자. Designed by Fraccino.

티스토리툴바