포도밭 개발자

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net C++ 소스 코드 #include #include #include #include using namespace std; int n,k; struct pos{ int x,y,d; }; vector v; const int dx[]={0,0,-1,1}, dy[]={1,-1,0,0}; int a[13][13]; string mp[13][13] = {""}; bool move(int x, int y,..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻�� www.acmicpc.net 전체 유저의 수가 최대 100이기 때문에 O(N^3)인 플로이드 와샬 알고리즘을 이용해 풀이했습니다. C++ 소스 코드 #include #define INF 500000 using namespace std; int d[101][101]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.ti..

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 메모이제이션을 활용해 DP로 풀이하였습니다. C++ 소스 코드 #include #include using namespace std; int cache[61][61][61]; int dp(int s1, int s2, int s3){ if (s1 > n; fill(&cache[0][0][0], &cache[60][60][60]+1,-1); int scv[3] = {0,0,0}; for(int i=0;i> sc..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net BFS로 풀이하였습니다. visit[x][y][0]은 벽을 하나도 부수지 않고 (x,y)에 도달했을 때의 최단거리, visit[x][y][1]은 벽을 하나 부순 상태에서 (x,y)에 도달했을 때의 최단거리입니다. a[x][y]일 때 이미 벽을 지난 상태 & a[nx][ny] 가 벽일때 : 이동 불가 (wall 과 a[nx][ny]의 합이 2인 경우) a[x][y]일 때..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 3차원 BFS로 풀이했습니다. C++ 소스 코드 #include #include #define MAX 101 using namespace std; const int dx[]={0,0,-1,1,0,0}; const int dy[]={-1,1,0,0,0,0}; const int dz[]={0,0,0,0,1,-1}; int a[MAX][MAX][MAX]; struct pos { ..

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 다이나믹 프로그래밍을 이용해 풀이하였습니다. 현재 칸 i에서 갈 수 있는 칸 j까지 최소 점프 횟수를 갱신해줍니다. C++ 소스 코드 #include #include #define MAX 1002 using namespace std; int n; int a[MAX],d[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr BFS를 이용해 풀이하였습니다. 현재 거리에 있는 노드들의 수를 업데이트 해주면서 마지막으로 업데이트 된 노드의 수가 반환됩니다. C++ 소스 코드 #include #include #include #define MAX 20001 using namespace std; bool visited[MAX]; int solution(int n, vector edge) { int answer = 0; vector adj[MAX]; for(int..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 경로를 압축한 유니온 파인드 알고리즘을 이용해 풀이하였습니다. C++ 소스 코드 #include #define MAX 1000001 using namespace std; int parent[MAX]; int find(int x){ if (x == parent[x]){ return x; } else { int y = find(parent[x]); parent[x..