홍시홍의 프로그래밍

분류 dp 요구사항 파도반 수열 구하기 풀이 파도반 수열은 1 1 1 2 2 3 4 5 7 9 .... 이런식으로 이루어져있다. 이는 d[n]=d[n-2]+d[n-3]으로 표현된다. 점화식만 찾는다면 쉬운 문제 long long 주의 #include using namespace std; long long d[110]; int n; int main() { int t; scanf("%d", &t); d[1] = 1; d[2] = 1; d[3] = 1; for (int i = 4; i

분류 다익스트라 요구사항 시작 위치에서 최소한의 시간으로 도착 위치로 도착하기 각 정점의 위치는 주어진다 풀이 정점에서 정점으로 이동하는데 최소거리가 되게 이동하기 -> 다익스트라 현재 정점에서 취할 수 있는 행동은 2가지이다 1. 도착 점까지 간다 2. 다른 정점으로 간다 크기가 100이니깐 모든 정점을 구하여 다익스트라를 사용할 수 있도록 한다. #include #include #include #include #include using namespace std; struct go { double x; double y; }; struct go1 { int x; double y; }; int n; go map[110]; vector v[110]; double dist[110]; double get_dis..

분류 : 이분 탐색 요구사항 효율적으로 돈을 사용하기 위한 최소 금액 구하기 풀이 아래 문제 요구사항은 인출하는 경우가 m보다 작으면 okay로 해석할 수 있다. 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 이분 탐색으로 금액을 정해보고 가능하다면 더 작은 금액을 찾아보고(정답 갱신) 불가능 하다면 더 큰 금액을 찾아서 답을 구한다. #include using namespace std; int n,m; int map[100100]; bool check(int val){ int money=val; int cnt=1; for(int i =0 ; i < n ; i++){ if(map[..

분류 : dfs/bfs 요구사항 N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다. -> dfs 진입하는 횟수 구하기 풀이 처음에 좌표를 +500,+500으로 잡으니 이어져있지 않더라도 옆에 있으면 이어지는 현상이 나타났다 해결 방법은 +500해주고 다시 *2를 해줌으로 직사각형 사이즈를 2배 증가 시켯다 이후는 단순히 2000*2000 배열을 dfs 탐색하면 된다 #include using namespace std; int n; int map[2200][2200]; int ans = 0; int dr[4] = { -1,0,1,0 }; int dc[4] = { 0,-1,0,1 }; void dfs(int r, int c) { //cout