백준 1672번 DNA 해독

문제 링크입니다: https://www.acmicpc.net/problem/1672

왜 DP 문제로 분류되어있는지 잘 모르겠는 문제입니다.

길이는 최대 백만이기 때문에 O(N)으로 충분히 해결할 수 있는 문제였습니다.

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

 

int N;

string change = "ACAGCGTAATCGGAGT";

 

char func(char a, char b)

{

        int idx = (a == 'A' ? 0 : a == 'G' ? 1 : a == 'C' ? 2 : 3);

        int idx2 = (b == 'A' ? 0 : b == 'G' ? 1 : b == 'C' ? 2 : 3);

 

        return change[idx * 4 + idx2];

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        string s;

        cin >> N >> s;

 

        for (int i = s.length() - 2; i >= 0; i--)

                 s[i] = func(s[i], s[i + 1]);

 

        cout << s[0] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~