본문 바로가기
반응형

코딩테스트34

[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] 백준 27884번 - 가희와 서울 지하철 3호선 (실버 1) 혼자 힘으로 풀었는가? X알고리즘 분류 - 수학 - 브루트포스 - 조합론 https://www.acmicpc.net/problem/27884 문제가희는 지하철을 타고 가다가 지상역과 지하역이 번갈아 나오는 롤러코스터 구간을 발견하였습니다. 롤러코스터 구간에 대한 정의는 아래와 같습니다.길이가 1인 구간은 롤러코스터 구간입니다.역 sa번, ... , sb번까지 롤러코스터 구간이고 아래 두 조건 중 하나를 만족하면 역 sa, ... sb+1번까지의 구간도 롤러코스터 구간입니다.sb번 역이 지상역이고, sb+1번 역이 지하역입니다.sb번 역이 지하역이고, sb+1번 역이 지상역입니다.예를 들어, 서울 지하철 3호선에서 제일 긴 롤러코스터 구간의 길이는 5입니다. 원흥, 원당, 화정, 대곡, 백석이 지하, 지상.. 2025. 6. 26.
반응형

티스토리툴바