밍맹의 생각날 때 적는 블로그

[문제 링크] 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬� www.acmicpc.net 오랫만에 알고리즘 문제 하나를 들고 돌아왔습니다. ( 약 2개월... ) 바로 시작하죠! 흐름은 다음과 같습니다. 입력받은 무게 N을 5로 나눈 몫을 5kg 봉지의 개수로 가지고 있는다. N을 5로 나눈 나머지를 3으로 나눈다 나머지가 0이 될 경우 나머지를 3으로 나눈 값을 3kg 봉지의 개수로 가지고 있는다. 나머지가 0이 되지 않을 경우에는 5kg 봉지의 개수를 하나 빼고 나머지 무게에 5kg을 추가한다. 다시 3으로 나누어서 나머지를 확인한다. 위..

[문제 링크] 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사용자에게 입력받은 수를 다음과 같은 조건으로 1로 만드는 최소 경우의 수를 찾으면 된다. 1을 뺀다 2로 나누어진다면 2로 나눈다. 3으로 나누어진다면 3으로 나눈다. 10을 예시로 들면 10 -> 9 -> 3 -> 1로 총 3번이면 1로 만들 수 있다. 이 문제는 다이내믹 프로그래밍(DP)으로 풀 수 있다. 다이내믹 프로그래밍이란 큰 문제를 작은 문제로 단순화시켜 해결하는 알고리즘이다. 10에서 1을 뺐을 경우 9가 된다. 여기서 우리가 만약 9가 1이 되는 최소 횟수를 알고 있다면?? (9가 1이 되는 최소 횟수) + 1 (10에서 1을 빼 9로 갈 때 횟..

[백준] 2667. 단지 번호 붙이기 문제 링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙..

문제가 너무 길고 그림이 많은 관계로 링크로 대체합니다. https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 총 4개의 톱니바퀴가 존재하고, 각각의 톱니바퀴 칸마다 N극(0)과 S극(1..

문제 오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오. 단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다. 하나의 문자를 입력하려면, 버튼을 눌러야 한다. 버튼을 누르면 버튼에 쓰여 있는 문자가 입력되며, 버튼을 누를 때마다 다음 문자로 바뀌게 된다. 예를 들어, 2를 누르면 A, 2번 누르면 B, 3번 누르면 C이다. 공백을 연속으로 누를 때는 기다릴 필요가 없다. 입력 첫째 줄에 p와 w가 주어진다. (1 ≤ p, w ≤ 1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자..