본문 바로가기

분류 전체보기

 (203)
7568번 덩치 기본적인 브루트포스 문제. 이지만 처음에 문제를 잘못이해하여 헤맸다. 단순히 본인보다 몸무게와 키가 큰 사람을 찾으면 된다. 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include using namespace std; struct Phy{ int tall; int weight; int order; }; int N; vector vec; void solved(){ for(int i=0;i> phy.tall; vec.push_back(phy); } solved(); for(int i=0;i
2210번 숫자판 점프 백트래킹 문제. 중복이 가능하기 때문에 방문 확인 없이 6자리라는 조건만 지키면 된다. 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #include #include #define MAX 6 using namespace std; typedef pair pir; int xx[4]={1,0,-1,0}; int yy[4]={0,1,0,-1}; char Num[MAX][MAX]; map m; int ans; void solved(string str, int x, int y){ if(str.si..
14888번 연산자 끼워넣기 브루트포스 문제. 연산자 우선 순위를 무시하고 계산하기 때문에 모든 경우의 수를 구해주면 된다. ex) 연산자 개수 1,1,1,0 이면 +,-,x 이기 때문에 나올 수 있는 경우의 수는 3!=6가지 이다. +,-,x +,x,- x,+,- x,-,+ -,+,x -,x,+ 이 순서대로 모든 숫자를 계산하여 최댓값, 최솟값을 구하면 된다. 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include #define MAX 101 using namespace std; int N; i..
1890번 점프 기본적인 DP + DFS 문제. 아래, 오른쪽 두개의 방향만 생각해서 풀면 된다(계속 네 방향을 고려해서 문제를 푸는데 오래 걸렸다). 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #define MAX 101 using namespace std; int N;int map[MAX][MAX];int xx[2]={1,0};int yy[2]={0,1};long cnt[MAX][MAX]; void solved(int x, int y){ if(cnt[x][y]!=-1){ return; } if(x==N-1 && y==N-1){ cnt[x][y]=1; return; } cnt[x][y]=0;..
1965번 상자넣기 기본적인 DP 문제(11053번, 11055번 문제와 같다). 증가하는 부분 수열을 구하면 된다. 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 28 29 30 31 32 33 34 35 36 37 38 #include #include #define MAX 1001 using namespace std; int N; int A[MAX]; int cnt[MAX]; void solved(){ for(int i=0;i
2225번 합분해 기본적인 DP문제. 주어진 예시를 풀어보자 N=20, K=2 -> 20 + 0, 19 + 1, 18 + 2, ....., 0 + 20 -> 즉, 21개이다. 정답을 DP[N][K]라고 할때 우리는 DP[N-0][K-1] + DP[N-1][K-1] + ..... + DP[N-N][K-1]까지 더하면 된다. 즉, DP[N][K]+=DP[N-정수][K-1] 라는 점화식을 구할 수 있다. 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 28 29 30 31 32 33 34 #include #define mod 1000000000 #define MAX 201 using namespace std; int dp[MAX][MAX]; int..
1517번 버블소트 버블 소트를 실행했을 때 swap한 횟수를 구하면 된다. 버블 소트를 그대로 구하면 시간 초과가 발생한다(시간 복잡도 O(n^2)이기 때문에) 머지 소트를 이용해 swap하는 횟수를 구하면 된다. ex) 5 4 3 2 1 -> 4 5 3 2 1 5와 4를 비교하여 1번 이동 -> 3 4 5 2 1 3과 4,5를 비교하여 3이 2번 이동 -> 3 4 5 1 2 1과 2를 비교하여 1번 이동 -> 1 2 3 4 5 1과 3,4,5를 비교하여 3번 이동 + 2와 3,4,5를 비교하여 3번 이동 총 1+2+1+3+3 = 10번 이동을 하게 된다. 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 28 29 30 31 32 33 34 ..
11404번 플로이드 기본적인 플로이드 와샬 문제. 플로이드 와샬을 구현할 수 있으면 그냥 풀 수 있다. ps. i에서 j로 가는 길이 하나가 아닐 수 있기 때문에 그것만 조심하면 된다(최소값을 찾아서 넣어주면 된다) 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #define INF 987654321 #define MAX 101 using namespace std; int n,m; int map[MAX][MAX]; void floydWarshall(){ for(int k=1;k

티스토리툴바