본문 바로가기

분류 전체보기

 (157)
#1932 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 실버 1의 문제이다. 언제쯤 dp문제 푸는 감을 익힐수 있을까 ㅜ. #include #include using namespace std; int dp[501][501]; int triangle[501][501]; int main() { freopen("input.txt","r",stdin); int maxnum=0; int n; //삼각형의 크기 cin>>n; for(int i=1;itriangle[i][j]; } } dp[1][1]=triangle[1][1]; //왼..
#2579 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 실버 3의 문제이다. 항상 느끼지만 dp는 감을 잡기가 어려운것 같다. 이 문제도 한참을 고민하다가 코드를 짰는데 틀리고, 다시 고민하다가 결국 정답코드를 보았다. 😥 #include #include using namespace std; int dp[301]; int score[301]; int main() { freopen("input.txt","r",stdin); int n; cin>>n; for(int ..
#1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 실버 3의 문제이다. 왜 실버 3인지 모르겠다 DP치고 쉬워서 그런가? 아직 디피가 익숙치않은 나에게는 굉장히 어려웠다. 재귀함수를 구성하는방법부터 어려워서 응애.. #include #include using namespace std; int memo[1000000]; int go(int n){ if(n==1) return 0; if(memo[n]!=0) //메모이제이션 return memo[n]; memo[n]=go(n-1)+1; if(n%2==0){ int temp = go(n/2)+1; if(memo[n]..
#9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 실버 3의 문제이다. 문제 자체는 굉장히 쉽지만 dp를 사용한다는 점에서 실버3인것같다. 또한 수가 기하급수적으로 커지기 때문에 int형으로는 해결할 수 없었다. #include using namespace std; long long memo[101]; long long pado(int n){ if(n3){ if(memo[n]!=0) return memo[n]; else if(memo[n]==0){ m..
#9184 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 실버2의 문제였다. 재귀함수를 저렇게나 많이 돌리는데 시간 제한이 1초??? 이건 dp다. 그리고 재귀를 쓰는 함수면 일단 dp를 고민해보는것도 좋은것 같다. 계산 시간을 확 줄여주는데 도움을 주니까~ #include using namespace std; int memo[51][51][51]; int w(int a,int b,int c){ if(a20) return w(20,20,20); else i..
#1904 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 실버 3의 문제였다. 문제는 굉장히 어려워보였는데 끄적끄적하니까 쉬웠다. 처음에는 이걸 직접 구하면서 카운트하는 변수를 하나씩 더해야하나? 이생각을 했었는데 dp의 방법이 전혀 아닌거같았다. dp인건 어떻게 알았냐면, 사실 dp탭으로 들어와서 알기는 했는데 제한시간이 0.75초 이면 무지~~엑건 dp문제인거 같았다. 암튼! #include #include using namespace std; long ..
#1003 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 실버 3의 문제이다. 피보나치 함수는 재귀를 통해 쉽게 구할 수 있지만 재귀를 이용하면 불필요한 계산이 숫자가 늘어날 수록 기하급수적으로 많아져 시간이 오래걸린다. 이 문제는 DP를 이용(메모이제이션을 이용)하여 푸는 문제였다. #include using namespace std; int memo[41]; int cntone; int cntzero; int fibo(int n){ if(n==0){ cntzero++; return 0; } else if(n==1){ cntone++; return..
#1926 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 실버 1의 문제다. 이제 실버1쯤은 쉽게(?) 풀 수 있을 것 같다. 문제는 간단하게 그래프에서 연결요소의 개수를 구하고 그 중에서 가장 넓이가 큰 영역을 출력하는 문제다. #include #include using namespace std; int n,m,cnt; int area;//그림 넓이 최대 int value; int map[501][501]; int visited[501][501]; int ..

티스토리툴바