Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 풀이) dp문제+배낭문제이다. dp[i][j]=k 를 i명이 h높이를 만들 수 있는 경우의 수를 k라고 하자. i명의 사람이 j높이 만큼 쌓을 수 있는 경우의 수는, i-1명이 j-(i번째 사람이 들고있는 현재블록의 높이) 만큼 쌓을 수 있는 경우의 수와 동일하다. 예를들어 4번째 사람이 들고있는 블록의 높이가 2,4라고 했을 때, 4명의 사람이 10만큼의 높이를 쌓는 경..

2021. 3. 11.

문제풀이/백준oj

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이) 문제를 읽어보니 1) 제일 작은 수+두번째로 작은수 2) 1번에서 구한 수 + 그다음 작은 수 3) 2번에서 구한 수 + 그다음 작은 수 4) 3번에서 구한 수 + 그다음 작은 수 ..... 가 된다. 따라서 우선순위 큐에 모든 수를 넣은뒤에, 작은수부터 2개씩 꺼낸뒤, 더해준 결과를 sum에 저장시키고, 더해준 결과를 다시 우선순위 큐에 넣어준다. 이때 우선순위 큐의 사이즈가 1이 될때까..

2021. 3. 9.

문제풀이/백준oj

www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 풀이) dp문제중 배낭문제이다. dp[i][j]=k(i명의 학생들이 j높이 만큼 쌓을 수 있는 경우의수 k)를 만족하는 dp배열 dp[51][51]을 설정해준다. 이떄, 모든 dp[i][0] (1>h; cin.ignore(1); for(int i=1;i

2021. 3. 6.

문제풀이/백준oj

4485번 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이) 다익스트라 알고리즘을 통해 (0,0) 부터 (N-1,N-1)까지 최소한의 검정루피를 얻는 경로를 구해주면된다. 시간복잡도) 시간복잡도는 최악의 경우 모든 x,y좌표를 큐에 넣고 연산하는 작업을 해야하므로 O(N*N) 이 된다. 코드) #include #include #define MAX 987654321 using namespace std; int..

2021. 1. 10.

문제풀이/백준oj

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이) 이문제도 일단 모든 정점에서부터 다른 모든정점까지의 최단거리를 구해주는Floyd-warshall 알고리즘을 적용시킨뒤, 1->v1->v2->N 과 1->v2->v1->N중 더 작은 수를 출력해주면 된다. 코드) #include #include #define MAX 987654321 using namespace std; int n, m; int v1, v2; i..

2021. 1. 10.

문제풀이/백준oj

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net n과 m값이 작아서 bfs미로찾기로 해서, 해당 maze[i][j]마다 지나오며 부셨던 벽의 최소값을 저장해둔뒤, 도착지점의 최솟값을 출력하는 방식으로 짜보았다. #include #include #include #define MAX 100*100+1 using namespace std; int maze[100][100]; int result[100][100]; int check[100][1..

2020. 12. 29.

문제풀이/백준oj

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net O(logN)의 시간이 걸리는 이진탐색을 생각해봤다. 숫자의 범위는 항상 1~N*N까지 이다. 1~N*N의 중앙값을 m이라 설정한뒤에 m보다 작거나 같은 수의 개수를 구해준다. 이때 m>=i*j인 값을 카운트 해줘야되기때문에 m/i가 저 조건을 충족시키는 j의 숫자가 된다. 하지만 한 행에서 m/i의 개수가 N이상으로 커질 수 없기 때문에 min(m/i,N)을 해준다. 이 결과에 ..

2020. 12. 29.

문제풀이/백준oj

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 이 문제는 그래프의 합집합을 이용하여 문제를 풀었다. 이어져 있는 도시들중 가장 낮은 도시로 부모를 설정을 해둔뒤, 마지막에 M개의 도시들의 부모 도시가 같으면 YES, 같지 않다면 NO를 출력하면된다. #include #include #include using namespace std; int arr[200][200] = { 0 }; vector v; int parent[200]; int getParent(i..

2020. 12. 29.