본문 바로가기

Wook's 개척일기234

[백준 5585번 : 브론즈 2] 거스름돈 (그리디 / Java) 이번 문제는 기본적인 그리디 알고리즘 문제라서 금방 풀수 있었던것 같다. 문제를 살펴보자. 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 문제 접근 방법 이번 문제는 그리디하게 문제를 풀어야 하기 때문에 제일 먼저해야할것은 가장 큰 액수부터.. 2021. 7. 27.
[백준 11726번 : 실버3] 2xn 타일링 (DP/Java) 이번 문제는 기본적인 DP를 물어보는 문제였다. 사실 처음에 어떻게 풀어야 하나 싶었는데 1부터 한번 방법의 수를 확인해보니 피보나치와 같은 결과가 나온다는걸 알고 금방 풀수 있었다. 그럼 이제 문제를 살펴보자. 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제 접근 방법 일단 이번 문제는 시간제한을 되게 1초 준거보면 일단 시간을 최대한 줄여야 한다. 시간을 줄일수 있는 방법에는 이분탐색, DP가 있는데 나는 이번 알고.. 2021. 7. 27.
[백준 2606번 : 실버3] 바이러스 (DFS/Java) 이번 문제는 기초 DFS 문제였어서 금방 풀수가 있었다. 문제를 살펴보자. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정.. 2021. 7. 27.
[백준 1541번 : 실버2] 잃어버린 괄호 ( 그리디 / Java) 이번 문제는 생각보다 쉽게 풀수 있는 문제였는데 내가 조금 어렵게 생각해 약간의 힌트(사실상 정답)을 받고 문제를 풀었다. 이번 문제는 약간의 수학적인 사고만 있다면 금방 풀수 있는 문제이다. 그럼 이제 문제를 살펴보자. 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.. 2021. 7. 27.

티스토리툴바