Baekjoon

[11399] ATM

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 🔎 해결 방법 오랜만에 한번에 맞은 문제 ㅋㅋ 문제를 읽어보면 바로 어떻게 풀어야 하는지 감을 잡을 수 있다. 줄을 [2, 5, 1, 4, 3] 순서로 세우는 것은 결국 돈을 인출하는데 걸리는 시간을 [1, 2, 3, 3, 4] 와 같이 오름차순으로 정렬하겠다는 소리이다. 그래서 중첩 for문을 사용해서 그냥 다 더해주면 끝~ 💡 내 코드(C++) // [11399] ATM // https://www.acmicpc.net/pr..

[11047] 동전 0

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘을 사용하는 문제! 그냥 간단한 문제였다. 💡 내 코드(C++) // [11047] 동전 0 // https://www.acmicpc.net/problem/11047 // 그리디 알고리즘 #include using namespace std; int main(void) { int n, k; // 준규가 가지고 있는 동전의..

[1931] 회의실배정

https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘을 사용하는 문제.... dp문제를 많이 풀다가 그리디 알고리즘 문제를 풀려고 하니 자꾸 dp식으로 접근하는 바람에 시간초과가 계속 났었다. 그리디 알고리즘이란, 현재 상태에서 가장 최선의 선택인 것만 골라서 진행하는 알고리즘이다. 즉 다른건 아무것도 생각하지말고 그냥 현재 상태에만 집중하면 되는 것이다. 🔎 해결방법 1. 회의 시작 시간을 기준으로 오름차순 정렬, 시작 시간이 같다면 끝나는 시간이 빠른 것부터 정렬(sort 함수 사용) 2. tmp을 회의가 가장 늦게 시작하는 시간으로 초기화 3. ..

[2668] 숫자 고르기(C++)

🌿 문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 🌿 해결 방법 directed graph에서 cycle의 개수와 cycle을 구성하는 노드를 찾는 문제이다. 이것도.... 한참 해보다가 결국 구글링을 하긴 했다.... dfs의 매개변수로 시..

[10451] 순열 사이클(C++)

문제 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 해결 방법 계속 런타임 에러가 떠서 for문이 너무 많은건가.... 변수형을 잘못 선언했나..... 한참을 찾아보고 질문도 올려보고 검색도 해봤는데 그냥 배열의 크기를 잘못 설정해서 그런거였다ㅋㅋ 문제에서 순열의 크기는 최소 2, 최대 1000 이라고 했는데 이걸 착각하고 배열의 크기는 1000-2+1해서 999면 충분하다고 생각했다. 왜 그랬지? 아무튼 그래프 정점의 시작 노드는 1번..

[11501] 주식

https://www.acmicpc.net/problem/11501 11501번: 주식 문제 홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁 www.acmicpc.net 💡 내 코드(C++) /*[11501] 주식*/ #include #define MAX 1000001 using namespace std;..

[2225] 합분해(C++)

문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결 방법 dp[i][j] = 0 ~ i까지의 정수 j개를 더해서 그 합이 i가 되는 경우의 수 내 코드(C++) // [2225] 합분해 // https://www.acmicpc.net/problem/2225 // dp // dp[i][j] = 0 ~ i까지의 정수 j개를 더해서 그 합이 i가 되는 경우의 수 #include using namespace std; int main(void) { long dp[201][201]; int n, k; cin >> n >> k; for (int i = 0; i < 201; i++) { dp[0][i] = 0; dp[1][i] = i; dp[..

[2193] 이친수

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 내 코드(C) #include #define MAX 1000000 int main(void) { int n; long dp[MAX]; dp[0]=0, dp[1] = 1, dp[2] = 1; scanf..