anonymous?

📝 문제풀이 과정 최소의 동전 개수가 되려면 가장 큰 동전부터 사용해야 한다. 따라서 배열 A 끝에서부터 탐색을 하고, A[i] > K이면 continue한다. 그렇지 않으면 count에 K / A[i], 즉 A[i]에서 최대로 사용할 수 있는 동전 개수를 더하고, 그만큼 K % A[i]를 K를 줘서 이미 할당한 것은 제외했다. 💻 C++ 제출코드 #include using namespace std; int main(){ int N,K, count=0; // N: 동전의 종류, K: 가치의 합 scanf("%d %d", &N, &K); int A[N]; for(int i=0; i=0; i--){ if(A[i] > K) continue; count += K / A[i]; K %= A[i]; } printf..

PROGRAMMING/Algorithm 2021. 2. 26. 21:11

📝 문제풀이 과정 visited: 방문여부 체크 1 2 3 4 5 6 7 3 1 3 7 3 4 6 1(current)이 3(next)을 지목했지만, 3(current)에서 3(next)을 지목했기 때문에 3 혼자서만 팀이고 1은 팀이 되지 못한다. 반례 6 2 3 4 5 6 2 output : 1 5 2 5 4 5 2 output : 3 6 1 3 4 3 2 6 output : 2 13 2 4 5 2 4 1 8 9 10 11 9 10 10 output : 8 10 2 5 7 1 6 8 8 3 5 10 output : 6 10 2 7 10 5 3 3 9 10 6 3 output : 8 6 2 1 1 2 6 3 output : 4 #include #include #include using namespace ..

PROGRAMMING/Algorithm 2021. 2. 26. 19:34

📝 문제풀이 과정 이렇게 37, 58, 89, 145, 42, 20, 4, 16이 반복된다. 2번 이상 반복되고, 3번째로 반복되기 시작하면 그때 리턴한다. 그리고 visited에서 1인 것은 반복되지 않는 것이므로 카운팅해서 답을 구한다. 각 single digit은 이전 숫자에서 % 10을 하고, (이전 숫자/ 10) % 10으로 반복해서 make_sum 함수에서 다음 숫자(next)를 구해줬다. 주의해야 할 점은, 제곱근을 pow로 구할 때 int 형으로 형변환을 해줘야 맞았다는 것을 받을 수 있다. 반례 입력1] 57 2 출력1] 4 입력2] 153 3 출력2] 0 입력3] 58 2 출력3] 0 💻 C++ 제출코드 #include #include #include #include using name..

PROGRAMMING/Algorithm 2021. 2. 26. 14:16

📝 문제풀이 과정 순열 사이클은 시작 후 자기 자신으로 다시 돌아온다. 1 2 3 4 5 6 7 8 3 2 7 8 1 4 5 6 주어진 예시를 보면, index마다 값이 주어지는데, 각 인덱스에서 값의 방향으로 간선이 존재한다. 이것으로 그래프의 연결성을 나타낼 수 있고, 1 -> 3, 3 -> 7, 7 -> 5, 5 -> 1로 1로 시작해서 1로 다시 돌아오므로 순열 사이클에 해당한다. 2의 경우에도 2에서 시작해서 2로 끝나므로 하나의 순열 사이클이다. 4 -> 8 -> 6 -> 4이므로 이 경우에도 하나의 순열 사이클로, 이 테스트케이스에는 총 3개의 순열 사이클이 존재한다. 방향 그래프이고, 모든 정점이 연결되어 있진 않으므로 모든 인덱스에 대해 방문하지 않았으면 BFS로 방문해서 탐색하도록 한다..

PROGRAMMING/Algorithm 2021. 2. 25. 17:19

📝 문제풀이 과정 BOJ:11724(연결 요소의 개수) 문제와 유사하다. 이 문제에서는 아래와 같은 조건을 확인하는 과정이 추가된다. 이분 그래프 확인 방법 서로 인접한 정점은 서로 다른 색이다. 현재 탐색을 시작한 정점과 인접한 정점은 +, -로 다른 부호를 준다. 현재 탐색한 정점의 값이 current이면, 해당 정점에는 current 값을 주고, 해당 정점과 인접한 정점은 -current를 줘서 서로 다른 그룹에 속하도록 한다. 정점과 인접한 정점을 방문할 때 만약 같은 색이라면 이분 그래프가 아니다. 현재 탐색 정점과 인접한 정점 중에서 이미 방문을 했고(color[num] != 0), color[num] + color[current] != 0이 아니라면 같은 그룹에 속하는 것으로 이분 그래프가 ..

PROGRAMMING/Algorithm 2021. 2. 25. 16:19

📝 문제풀이 과정 BFS로 구현을 했고, visited[i] == false일 때마다 탐색을 하고, 탐색이 끝나면 연결이 없는 것이기 때문에 ++count를 반환해줬다. 고려해야 하는 것 간선의 수가 하나도 없는 경우 정점도 하나의 연결 요소로 간주한다. => BFS 함수 들어가서 visited 체크하고, ++count하고 나온다. 양방향 그래프이므로 그래프 만들 때 u에 v 넣었으면 v에도 u를 넣는다. 질문에 있는 테스트케이스마다 다 맞는데 45%에서 계속 틀리게 나와서, visited를 초기에 false로 모두 초기화하니까 맞았다... (초기화는 확실히...) 테스트케이스 입력1] 5 1 1 2 출력1] 4 ------------ 입력2] 6 2 3 4 4 2 출력2] 4 ------------ 입..

PROGRAMMING/Algorithm 2021. 2. 25. 02:33

📝 문제풀이 과정 N/K 1 2 3 4 1 1 2 3 4 2 1 3 6 10 3 1 4 10 20 4 1 5 15 35 DP[N][K]: 0부터 N까지의 정수 중에서 K개의 수로 N을 만드는 경우의 수 DP[1][1]부터 DP[4][4]까지의 경우의 수를 구해보면, 일반화된 점화식을 구할 수 있다. DP[i][1] = 1 : 모든 수 N에 대하여 K = 1일 때 경우의 수는 1이다. DP[1][i] = i : 모든 수 1에 대하여 K = i일 때 경우의 수는 i이다. N = 2, K = 2부터는 DP[N][K] = DP[N-1][K] + DP[N][K-1] 라는 점화식을 가질 수 있다. j의 범위는 K 이하까지이다. (그 이후로 되면 out of range로 쓰레기 값이 나온다..) 매 DP[i][j]마..

PROGRAMMING/Algorithm 2021. 2. 23. 23:26

📝 문제풀이 과정 주어진 예제에서 카드 1장, 2장, ... , N장을 선택할 때 가질 수 있는 가장 큰 금액을 구해서 일반화된 식을 만들었다. DP[i]: 카드가 i장일 때, 지불할 수 있는 가장 큰 금액 N = 4, P = {1, 5, 6, 7} 이라고 하자. DP[1]은 카드 1장을 선택했을 때 지불 가능한 가장 큰 금액으로, 1장일 때 금액 1원이 최대 금액이다. DP[1] = 1 DP[2]는 카드 2장을 선택했을 때 가장 큰 지불 금액으로, 1장*2, 또는 2장짜리를 살 수 있다. 2와 5 둘 중에서 5가 더 크므로 DP[2] = 5 (DP[i]를 가져감) DP[3]은 3장 짜리 선택(6), 또는 2장짜리 + 1장짜리(6), 1장짜리와 2장짜리(6) 중이므로 DP[3] =6 DP[4]의 경우, ..

PROGRAMMING/Algorithm 2021. 2. 23. 18:56

📝 문제풀이 과정 P(n) = 1 (0 = 3) 0 이상 2 이하의 수에 대해서는 1의 값을 갖고, 3 이상부터는 점화식 F(n) = F(n-2) + F(n-3) 이 된다. n = 3 P(3) = P(1) + P(0) = 1 + 1 = 2 n = 4 P(4) = P(2) + P(1) = 1 + 1 = 2 n = 5 P(5) = P(3) + P(2) = 2 + 1 = 3 n = 6 P(6) = P(4) + P(3) = 2 + 2 = 4 n = 7 P(7) = P(5) + P(4) = 3 + 2 = 5 n = 8 P(8) = P(6) + P(5) = 4 + 3 = 7 n = 9 P(9) = P(7) + P(6) = 5 + 4 = 9 n = 10 P(10) = P(8) + P(7) = 7 + 5 = 12 ....

PROGRAMMING/Algorithm 2021. 2. 23. 14:42

📝 문제풀이 과정 N이 홀수인 경우 2 x 1, 1 x 2 타일을 채울 수 없다. DP[N] = 0 N이 짝수인 경우 DP[i] = DP[n-2]*3 : DP[n-2]에서 3 x 2에 대해 3가지 경우가 존재한다. 4 이상의 짝수인 경우에, 위와 같은 형태가 2개씩 존재한다. 💻 C++ 제출코드 #include #include using namespace std; int main(){ int N; scanf("%d", &N); deque DP(N+1, 0); DP[0] = 1; DP[2] = 3; if(N%2 !=0 ) DP[N] = 0; // N == 홀수 // N == 짝수 for(int i=4; i= 0; j -= 2) DP[i] += DP[j]*2; } printf("%d", DP[N]); } D..

PROGRAMMING/Algorithm 2021. 2. 23. 01:15

📝 문제풀이 과정 DP[i] : 숫자 i에서 제곱수 항 최소 개수 주의할 점이, 지금까지 항상 인덱스 0부터 시작해서 0을 숫자 1로 해서 하려고 했는데, 7 이상부터는 수가 잘 안 맞았다. +1을 하면 7 이전 숫자들에서 안 맞고, 1을 더하지 않으면 7부터가 안 맞는다. 그래서 인덱스를 숫자 그대로 했더니, DP[i] = min(DP[i], DP[i-j*j]+1)에서 4에서는 DP[4-2*2] + 1 = 0 + 1 =1, 7도 DP[7-4] + 1 = 4로 제대로 나온다. j*j

PROGRAMMING/Algorithm 2021. 2. 22. 22:20

📝 문제풀이 과정 BOJ:2156번(포도주 시식) 문제를 참고해서 점화식을 생각했다. 점화식에서 DP[i-3]이 사용되므로, 0~2번째에 대한 초기값이 필요하다. DP[0] = A[0] DP[1] = max(A[1], A[1] + A[0]) DP[2] = max(A[1] + A[2], A[0] + A[2]) 3번째부터는 점화식을 사용한다. i-1번째를 포함하는 경우 DP[i] = DP[i-3] + DP[i-1] + DP[i] i-1번째를 포함하지 않는 경우 DP[i] = DP[i-2] + DP[i] 이 두 경우에 대한 max 값을 DP[i]로 가져간다. A[0] 10 A[1] 20 A[2] 15 A[3] 25 A[4] 10 A[5] 20 위와 같이 테스트케이스가 있을 때, DP[3]부터는 A[0] + A..

PROGRAMMING/Algorithm 2021. 2. 22. 17:10