본문 바로가기

Algorithm Problems

 (212)
[백준/C++] 1005번: ACM Craft 문제https://www.acmicpc.net/problem/1005문제 요약1번부터 N번까지 각 N개의 건물을 짓는데 걸리는 시간이 주어진다. 또한 건설 순서 X Y가 주어진다.(X Y: 건물 X를 지은 다음 건물 Y를 짓는 것이 가능하다.) 특정 건물 W를 입력 받고, 해당 건물이 가장 빨리 지을 때까지 걸리는 최소시간을 출력한다. 건물들은 가능하다면, 동시에 지어질 수 있다.코드#include #include #include #include #include #include using namespace std;// indegree[i]: i번 노드로 들어오는 간선의 수int indegree[1010];// delay[i]: i번 노드의 지연 시간int delay[1010];// dp[i]: i번 노드..
[백준/C++] 11404번: 플로이드 문제https://www.acmicpc.net/problem/11404문제 요약n개의 도시가 있다. 한 도시에서 다른 도시에 도착하는 m개의 버스가 있다.  각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍에 대해 도시 A에서 B로 가는데 필요한 비용의 최솟값을 출력한다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.코드#include #include #include #include #define INF 1e9using namespace std;int n, m;int dist[110][110];vector> edges[110];int main() { cin >> n >> m; // 그래프 입력 for (int i = 0; i > a >> b >> w; ..
[백준/C++] 2206번: 벽 부수고 이동하기 문제https://www.acmicpc.net/problem/2206문제 요약N × M 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. (1, 1)에서 (N, M)으로 최단 경로로 이동하려 할 때, 벽을 1개 부술 수 있다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.코드#include #include #include #include #include using namespace std;int n, m;int board[1010][1010];bool visited[1010][1010][2];int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };// x, y, dist, wallqueue> q;i..
[백준/C++] 2342번: Dance Dance Revolution 문제https://www.acmicpc.net/problem/2342문제 요약DDR(Dance Dance Revolution)은 아래와 같은 모양의 발판 위에서 주어진 스텝에 맞춰 나가는 게임이다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정한다. 게이머는 두 발을 중앙에 모으고 게임을 시작하면 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다.(두 발이 동시에 움직이지는 않는다.) 두 발이 같은 지점에 있는 것이 허락되지 않는다. 발이 움직이는 위치에 따라서 드는 힘이 다르다. 1. 중앙에 있던 발이 다른 지점으로 움직이면, 2의 힘을 사용한다.2. 다른 지점에서 인접한 지점으로 움직이면, 3의 힘을 사용한다.3. 반대편으로 발을 움직이면, 4의 힘을 사용한다.4. 같은 지점을..
[백준/C++] 2252번: 줄 세우기 문제https://www.acmicpc.net/problem/2252문제 요약N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키가 주어지지 않고, 두 학생의 키를 비교 결과가 M개 주어졌을 때 줄을 세우는 방법을 출력한다. 답이 여러 가지인 경우 아무거나 출력한다.코드#include #include #include #include #include #include using namespace std;int N, M;vector edges[32032];// indegree[i]: i번 노드로 들어오는 간선의 수int indegree[32032];queue q;int main() { cin >> N >> M; // 그래프 입력 while (M--) { // a번 학생이..
[백준/C++] 5582번: 공통 부분 문자열 문제https://www.acmicpc.net/problem/5582문제 요약두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열의 길이를 출력한다. 예시문자열 A = "ABRACADABRA"문자열 B= "ECADADABRBCRDARA" 가장 긴 공통 부분 문자열은 "ADABR"이고, 길이는 5이다.코드#include #include #include #include using namespace std;// dp[i][j]: 문자열 A에서 i번째 문자, 문자열 B에서 j번째 문자에서 끝나는 가장 긴 공통 부분 문자열 길이int dp[4040][4040];string A, B;int res;int main() { cin >> A >> B; for (int i = 1; i ..

티스토리툴바