Victoree's Blog

Concept & Idea 어찌됫든 수열이다. 어떻게든 풀어보려고 규칙을 찾으려 했더니 간단한 문제였다. 원래는 dp배열을 2차원으로 만들어서, 변을 공유했는지 안했는지 체크하는 3개의 col을 만드려했는데, 규칙이 보이지 않아서 바로 문제를 다시 읽어보았다. 그랬더니 새로 생성되는 수가 그냥, i-2와 i-3의 합으로 해결된다는 것을 알게 되었다. 왜 범위가 int를 넘어가는지 이해가 잘 안간다. 100밖에 안되는데.. 질문검색에도 어느 순간부터 int를 넘어간다는 대답밖에 없었다. 앞으로 dp문제를 풀고 틀리면 그냥 배열 범위를 바꾸어 봐야겠다… Code #include using namespace std; int t; long long p[101]; int main() { cin>>t; p[1]=1..

Concept & Idea 처음 주어진 32의 타일의 경우의 수가 3개이다. 하나 하나 쪼개서 생각해보면, 맨 처음 타일이 왔을 때 뒤에 3개를 다시 붙이면 다른 경우의 수를 만들 수 있다. 그래서 바로 생각할 수 있는 예시가, 3dp[i-2]이다. 그런데 이 3개만으로 끝나지 않고, 새로운 경우의 수가 2개씩 더 생겨난다. 그래서 2dp[i-4]+ 2dp[i-6]등등을 더해가는 것으로 문제를 해결 할 수 있었다. dp[0]을 1로 초기화해 둠으로 해결할 수 있었다. Code #include using namespace std; int n; int dp[31]; int main() { cin>>n; dp[0]=1; dp[2]=3; for(int i=4; i

Concept & Idea 처음에는 굳이 DP로 풀어야하나?라는 의문이 들어서 그냥 생각대로 풀었다. 수학문제 해결하듯이 풀어낸 코드는 다음과 같다. #include #include using namespace std; int n; int main() { cin>>n; int cnt=0; while(n!=0) { int t=int(sqrt(n)); n-=t*t; cnt+=1; } cout

Concept & Idea 연속합이라고해서 투포인터 개념을 이용해 문제를 해결하려 했는데, 그냥 간단한 이중 포문으로 해결하였다. 처음엔 아무 조건없이 이중포문으로만 해결하니, 시간초과를 마주하였는데 간단한 res>n; for(int i=1; i>map[i]; dp[i]=map[i]; } for(int i=1; i

Concept & Idea 조건은 생각보다 간단하다. 우선 증가하는지 보면되고, dp배열에 여태까지 기록한 가장 큰 증가 부분 수열의 값을 저장해놓으면 된다. 가장 큰 증가 부분 수열을 찾으면, 그 값에 자기 자신을 더한 값을 DP[i]에 저장하면 된다. Code #include using namespace std; int n; int map[1001]; int dp[1001]; int res=0; int main() { cin>>n; for(int i=1; i>map[i]; } for(int i=1; i

Concept & Idea 문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다. row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다. DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다. Code #include using namespace std; int t; int map[2][100001]; int cnt=0; int dp[2][100001]; int main() { cin>>t; for(int i=0; i..