본문 바로가기

분류 전체보기

BOJ)2688 줄어들지 않아 문제: icpc.me/2688 N자리 줄어들지 않는 숫자를 구하는 문제이다. dp테이블을 dp[pos][val]을 val로 끝나는 pos자리 줄어들지 않는 숫자의 수로 정의한 뒤 다이나믹 프로그래밍을 통하여 해결할 수 있다. long long을 사용하지 않는다면 overflow가 발생할 수 있다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;typedef long long ll;ll t, dp[100][10], n;ll func(ll pos,ll val) { if (val 9)return 0; if (pos == 1)return 1; ll &ret = dp[pos][val]; if .. 더보기
BOJ)2230 수 고르기 문제: icpc.me/2230 N개의 원소로 이루어진 수열에서 두 수를 뽑았을 때 그 수의 차이가 M보다 크면서 가장 작은 두 수의 차이를 구하는 문제이다. 우리는 정렬을 해준 뒤 투 포인터 i , j 를 설정하여 문제를 해결할 수 있다. a[i]-a[j]가 m보다 작다면 두 수의 차이가 더 커져야 하므로 i를 증가시키고 m보다 크거나 같다면 j를 증가시키는 방법으로 해결해나가면 된다. 1234567891011121314151617181920212223#include #include #define INF 1987654321using namespace std;int n, m, a[100001], r;int main() { scanf("%d%d", &n, &m); for (int i = 0; i 더보기
BOJ)9463 순열 그래프 문제:icpc.me/9463 두 순열이 주어질 때 같은 번호끼리 연결할 때 생기는 교점의 수를 구하는 문제이다. 우선 첫번째 순열의 순서를 기준으로 새로운 순열 A를 생성한다. 그리고 두번째 순열의 각 번호를 순열 A에 대입한 순열 B를 생성한다. 이제 순열 B에서 현재 보고있는 i보다 오른쪽에 있고 i로 인하여 만들어지는 교점의 수는 B[i]-1-(1~B[i]까지 이미 지나간 수들의 수)로 계산 가능하다. 1~B[i]까지 이미 지나간 수들의 수는 세그먼트 트리를 이용하여 관리할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;i.. 더보기
BOJ)2992 크면서 작은 수 문제:icpc.me/2992 등장하는 수로 조합가능 한 모든 수를 비교하여 그 중 최솟값을 구해주면 된다. 시간 복잡도는 O(6!)이다. 12345678910111213141516171819202122232425#include #include #include #include #define INF 987654321using namespace std;char a[7];int r = INF;int main() { scanf("%s", &a); int v = stoi(a); vector vt; for (int i = 0; a[i] != '\0'; i++) vt.push_back(a[i]); sort(vt.begin(), vt.end()); do { for (int i = 0; i 더보기
BOJ)1058 친구 문제: icpc.me/1058 2-친구수가 가장 많은 사람의 2-친구 수를 구하는 문제이다. 2-친구의 수는 플로이드 워셜을 통하여 구한 최단거리가 2이하인 모든 정점들의 합으로 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, a[51][51], r;char b;int main() { scanf("%d", &n); memset(a, 0x3f, sizeof(a)); for (int i = 1; i 더보기
BOJ)12100 2048 (Easy) 문제:icpc.me/12100 2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다. 하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다. 5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다. 이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950.. 더보기
BOJ)13460 구슬탈출2 문제: icpc.me/13460 빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다. 우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include using namespace std;int n, m, disc[11][11][11][11], bx, by, rx, ry;char a[11][11];int .. 더보기
BOJ)1520 내리막 길 문제:icpc.me/1520 지도에서 자기보다 숫자가 낮은 곳으로 이동할 수 있을 때 0,0에서 n-1 ,m-1로 갈 수 있는 경로의 개수를 출력하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 문제를 해결할 수 있다. dp[x][y]는 0,0에서 x,y로 이동할 수 있는 경로의 수라고 정의한 뒤 4방향 탐색으로 테이블을 채워나가면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int dx[] = { 0,0,-1,1 };int dy[] = { -1,1,0,0 };int n, m;int chk(int x, int y) { return 0 더보기
BOJ)10422 괄호 문제: icpc.me/10422 괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다. 이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다. N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다. dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다. 점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다. 123456789101112131415161718192021222324252627282930#include #include #include #define MOD 1000000007typedef long long ll;usin.. 더보기
BOJ)1194 달이 차오른다, 가자. 문제: icpc.me/1194 가중치 없는 그래프에서의 최단거리를 구해야 하므로 BFS를 이용하면 된다, 이때 열쇠라는 조건이 추가로 붙는데 우리는 열쇠를 쥐고 있는 상태를 비트마스킹을 통하여 표현해주면 된다. qu의 3번째 인자는 해당 상태가 가지는 열쇠를 비트로 표현한 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include using namespace std;int n, m, disc[51][51][1 더보기

티스토리툴바