본문 바로가기
반응형

Algorithm293

[Java/Python] 백준 4839번 - 소진법 (실버 3) 혼자 힘으로 풀었는가? O알고리즘 분류 - 정수 - 소수 https://www.acmicpc.net/problem/4839 문제 이해처음엔 문제를 보고 이게 뭔 말인가 이해가 안 되었다. 우선 해당 문제가 소수를 구해야 하는 문제임은 쉽게 파악할 수 있으니 소수를 구해보면 p0 = 2p1 = 3p2 = 5p3 = 7...이고 각 자릿수 ai는 다음 조건을 만족한다.0 ≤ ai ≤ pi - 1 예제 123으로 알아보자123 = a0 + a1*p0 + a2*p0*p1 + a3*p0*p1*p2 + ... 실제 정답은 다음과 같다.1 + 1*2 + 4*2*3*5 실제 적용이러한 과정이 도출되는 과정은 다음과 같다. 우선 이 문제를 풀기 위해선 소수들의 곱을 따로 저장해 두면 편하다.term[0] = p0 =.. 2025. 7. 15.
[Java] 백준 7481번 - ATM놀이 (실버 1) 혼자 힘으로 풀었는가? X알고리즘 분류 - 수학 - 정수론 - 비둘기집 원리 https://www.acmicpc.net/problem/7481 문제ATM에는 다른 종류 두 가지의 지폐가 굉장히 많이 있다. ATM에서 돈을 찾을 때 ATM은 예금주의 잔액을 넘지 않는 범위에서 정확한 양의 돈을 지급한다. 꿍은 지폐를 많이 들고다니고 싶지 않기때문에 되도록이면 가장 적은 수의 지폐를 들고다니고 싶어한다.여러분은 가장 적은 수의 지폐로 꿍이 인출하려는 금액을 정확히 지급해주는 ATM을 만들어야 한다. ATM을 만들 때, ATM안에는 무제한으로 지폐가 들어있다고 가정해도 좋다.입력첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있으며 각 줄에는 a, b(ATM에 있는 지폐의.. 2025. 7. 4.
[Java/Python] 백준 16562번 - 친구비 (골드 4) 혼자 힘으로 풀었는가? O알고리즘 분류 - 분리 집합 https://www.acmicpc.net/problem/16562 문제19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!위와 같은.. 2025. 7. 3.
[Java] 백준 28310번 - 고양이에게 과자 나눠 주기 (실버 4) 혼자 힘으로 풀었는가? O알고리즘 분류 - 수학 - 사칙연산 https://www.acmicpc.net/problem/28310 문제Albert는 고양이 N$N$ 마리를 키우고 있는데 편의상 번호가 1부터 $N$까지 붙어있다. 오늘은 간식으로 고양이용 과자 $M$개를 나눠주려고 하는데 각 과자는 1번 부터 M$M$번까지 번호가 붙어있고, 모두 동일한 크기이다. j$j$ 번째 과자는 균등한 크기의 $V_j$ 조각으로 쪼개져있고, 이는 $N$ 마리의 고양이들이 적절히 나눠먹는다 - $i$번째 고양이가 먹은 $j$번 과자 조각의 수를 $A_{j, i}$라 하자. 이 때, $\sum_{1 \le i \le N} A_{j, i} = V_j$ 를 항상 만족한다.예를 들어 $N = 3$, $M = 3$, $V = [.. 2025. 7. 2.
반응형