글 읽기 - ( c++ ) 어디가 틀린지 봐주실분 ㅠㅠ

sgy8971 5년 전 0

n = 4

m = 7 이면

m의 위에서부터 차례대로 다리를 놓게 되면

좌 1 - 우 1

좌 2 - 우 2

좌 3 - 우 3

은 고정상태이고
좌 4 - 우4,5,6,7 ==> 4개

그 다음에는

좌 1 - 우 1

좌 2 - 우 2

좌 3 - 우 4

은 고정상태

좌 4 - 우 5,6,7 ==> 3개

이런식으로 생각하여 문제를 풀었는데

전혀 다른 답이 나옵니다 ㅎㅎ ;;

이 알고리즘이 왜 틀린걸까요?

#include<iostream>
using namespace std;

int dp[31];
int main(){
    int n;
    cin >> n;
    
    for(int i=1; i<31; i++)
        dp[i] = i + dp[i-1];

    while (n--) {
        int n,m;
        cin >> n >> m;
        
        if( n == 1){
            printf("%d\n",m);
            continue;
        }
        int value = m-n+1;
        int ans = 0 ;
        for(int i=1; i<=value; i++){
            ans = ans + ( dp[i] * (value + 1 - i)) ;
        }
        printf("%d\n",ans);
    }
    return 0;
}

jh05013 5년 전 0

dp가 무슨 값을 나타내는 건지 모르겠습니다. 예시 말고 정확한 논리 과정을 설명해 주세요.

gaelim 5년 전 0

좋은 시도이지만, 20~23 번줄부터 조금 과 일반화를 하신것 같네요

두 인풋

2 5

3 5

결과값이 어떻게 될지 한번 손으로 그려보시겠나요?

sgy8971 5년 전 0

@gaelim

아 감사합니다 ㅠㅠ

맹점을 찾았습니다.

sgy8971 5년 전 0

@jh0513

질문 글을 너무 비논리적으로 썼네요 ... ㅠㅠ 죄송합니다

전체적으로 알고리즘이 잘못되었습니다.

다시 풀어보도록 하겠습니다

감사합니다 : )

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

( c++ ) 어디가 틀린지 봐주실분 ㅠㅠ

sgy8971 5년 전 0

jh05013 5년 전 0

gaelim 5년 전 0

sgy8971 5년 전 0

sgy8971 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말