글 읽기 - 이 문제를 DP로 푸는 방법이 있나요?

tna1595 5년 전 2

N 이 기껏해야 100만이고, 글자 하나하나 줄여갈 경우에 반복문이 기껏해야 100만번 도니까 5초면 너무너무 충분한 시간이라 생각해서

그냥 브루트 포스 느낌으로 하나하나 해도 될 거 같다는 생각으로 코드를 짜봤는데, 이게 문제 분류는 DP네요

DP로 풀어서 더 효율적인 방법이 있나요??

lakshimi 4년 전 0

저도 이게 궁금해서, 질문게시판을 읽게 되었네요. 제가 문제를 잘못 이해한 것인지 아닌지 확인차요.

hagtfms 3년 전 0

더 효율적이진 않은데 가능은 한 것 같아요

... 이거 dp 맞겠죠? ㅋㅋㅋ

그런데 이 소스는 그냥 하나씩 검사하는 거랑 똑같으니까 의미가 없는 것 같아요

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    string prevCh, str;
	map<string, string> m;
        
	m["AA"] = "A";
    m["GA"] = "C";
    m["CA"] = "A";
    m["TA"] = "G";

    m["AG"] = "C";
    m["GG"] = "G";
    m["CG"] = "T";
    m["TG"] = "A";

    m["AC"] = "A";
    m["GC"] = "T";
    m["CC"] = "C";
    m["TC"] = "G";

    m["AT"] = "G";
    m["GT"] = "A";
    m["CT"] = "G";
    m["TT"] = "T";

    scanf("%d\n", &n);
    getline(cin, str);

    prevCh = str.substr(n-1, 1);
    for(int i=n-2; i>=0; i--){
        prevCh = m[prevCh + str.substr(i, 1)];
    }
    printf("%s\n", prevCh.c_str());

	return 0;
}

hagtfms 3년 전 0

string이라 그런가 하고 char로 바꿨는데도 똑같이 8ms 걸리네요

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    char keys[3] = "AA";
    char prevCh;
    string str;
	map<string, char> m;
        
	m["AA"] = 'A';
    m["GA"] = 'C';
    m["CA"] = 'A';
    m["TA"] = 'G';

    m["AG"] = 'C';
    m["GG"] = 'G';
    m["CG"] = 'T';
    m["TG"] = 'A';

    m["AC"] = 'A';
    m["GC"] = 'T';
    m["CC"] = 'C';
    m["TC"] = 'G';
    
    m["AT"] = 'G';
    m["GT"] = 'A';
    m["CT"] = 'G';
    m["TT"] = 'T';

    scanf("%d\n", &n);
    getline(cin, str);

    prevCh = str[n-1];
    for(int i=n-2; i>=0; i--){
    	keys[0] = str[i];
    	keys[1] = prevCh;
    	prevCh = m[string(keys)];
    }
    putchar(prevCh);
	return 0;
}

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

문제

문제

출처

ICPC

이 문제를 DP로 푸는 방법이 있나요?

tna1595 5년 전 2

lakshimi 4년 전 0

hagtfms 3년 전 0

hagtfms 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말