코딩스토리

www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net KOALA의 이번 주 모의테스트 문제였다. 누가 봐도 DP 문제였다. 처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ 핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다. dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다. 나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다. 마법의 두루마리에 적힌 ..

www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 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 #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll dp[100004][4]; int t, n; dp[1][1] = 1; dp[1][2] = 0; ..

백준 14266번 - 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제는 BFS문제(다이나믹 프로그래밍을 사용한)이다. 최근 풀었던 BFS문제중에 가장 어려웠다. 처음에는 가볍게 queue에 pair로 현재 이모티콘 숫자와 클립보드의 개수를 받아서 풀어보려 했는데 문제의 조건 중 '클립 보드에 복사'라는 조건이 자꾸 걸렸다. 생각해보다가 2차원 배열을 사용하면 될 것 같아서 써봤는데 바로 틀렸습니다.. 디버깅해보니 너무 많은 ..

백준 12852번 - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 BFS, 다이나믹 프로그래밍 문제이다. 처음에는 top-down 방식으로 문제를 해결하려 했다. 문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다. 출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면 dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다. 코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botto..