미친수 이친수를 풀어보려고 한다.오마이갓 너무 쉬운 문제인데 엄청 헤맸다!!!!!!! 이참에 dp 문제에 대한 접근 방식을 확실히 해보려고 한다.     문제0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을..

학교에서 배운 DP 문제가 그대로 나와있었는데 C++로 풀어보는건 처음이기도 하고..이제 백준으로 제대로 DP에 접근해보려고 해서 가장 기본적인 문제를 가져왔다.        입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 지난 학기때 기억을 스멀스멀 해보니 해당 DP문제는 n=1, n=2 부터 차근차근 접근해나가면 된다.만약 ( 2 * 82 ) 라는 직사각형의 타일을 채우는 방법의 수를 구하라고 하면 매우 복잡해보이지만, 왼쪽부터 타일을 채워나간다고 생각하고 생각해보자.   D(n) = D(n-1) + D(n-2)// 2*n 크기 직사각형에 타일을 채우는 전체 경우의 수( 첫 타일이 가로인 경우의..

시간 초과가 발생한 이유와 함께 어떻게 풀이했는지 적어보려고 한다.      입력첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.출력첫째 줄에 남게 되는 카드의 번호를 출력한다.자료구조 문제인데 아직 자구를 배우지를 않아서 queue 대신 vector을 사용하다가 시간 초과가 발생했다. // 1. vec.erase(vec.begin()); // 2. vec.push_back(vec.front()); vec.erase(vec.begin()); 벡터 요소로 확인해봤을 때 문제에서 요구하는 핵심 형식은 다음과 같을 것이다. 1. N이라는 정수를 입력받는다. (이때 N은 500000만큼의 숫자가 될 수도 있다.) 2. 첫 ..

무리 없이 풀었던 문제지만 뭔가..뭔가.. 내가 기존에 작성한 코드보다 더 나은 방법이 있을 것 같다.그래서 다른 코드를 참고해보면서 개선점을 적어보기록 했다.그리디 알고리즘을 이용한 문제다.       입력첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.출력첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.  쉽게 말해서 연속되는 숫자는 한꺼번에 뒤집을 수 있다는 가정 하에,다솜이가 뒤집는 카운트의 최소 수는? 을 구하는 문제이다.(이때 주의해야할 점은 0을 뒤집었을 때, 1을 뒤집었을 때 전체에 대한 가장 최소의 수를 찾는 것이다.)      #include #include #include #include using namespace std;int sum0 = 0;int sum..

이전에 풀었던 문제와 제목이 비슷해보여서 친근해서 선택했다.이번에도 0을 찾아내는 문제다.    입력첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.출력재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다. 예를들어 4를 입력하면 총 4개의 숫자를 입력받게 되는데,이때 원소에 0이 포함되어 있다면 그 앞 가장 최근의 원소를 지우거나 카운트되지 않도록 해야 한다.(이때 그 앞의 원소도 ..