개발하는 햄팡이

https://www.acmicpc.net/problem/19951풀이 과정이 문제는 1년전에 풀었었는데 지금 다시 보니 생각이 안나서 풀어보기로 했다.문제를 보면 흙파기를 명령이 들어왔을 때 바로바로 하는게 아니라 한번에 모아뒀다가 파겠다는건데명령마다 구간이 다르기때문에어디는 3만큼 파야될수도 있도 어디는 5만큼 파야될 수도 있고, 덮기도 해야해서 각 칸마다 변화량이 다르다는 것이 문제이다. 그래서 명령이 들어오는 그대로 모든칸에 변화를 줘버리면 결국 계속 파내고 덮고 하는거나 마찬가지인셈이라서한번에 끝내야한다는 생각은 문제를 읽자마자 바로 든다. 이걸 어떻게 n만큼 기록을 안하고 최대한 o(1)로 해결할까?변화한 값을 매 칸마다 기록하는게 아니라 시작과 끝만 적용되도록 기록하면 된다. 예시를 보면첫번..

https://www.acmicpc.net/problem/11404풀이 과정해당 문제는 이름에 대놓고 쓰여있듯이 플로이드-워셜 알고리즘을 이용하여 간단하게 풀 수 있는 문제이다.그런데 플로이드 워셜 알고리즘 공부한지가 오래되어서 다시 공부할 겸 풀어볼려고 한다. 플로이드 워셜 알고리즘을 대충 기억하고 있는 사람의 눈으로 이 문제를 봤을때n개의 도시와 한 도시에서 출발해서 다른 도시에 도착하는 m개의 버스가 있는데 각 버스마다 비용이 다르고...모든 도시의 쌍(a, b)에 대해서 a->b로 가는데 필요한 비용의 최솟값을 구해야한다..뭔가 배열에 최솟값을 계속 갱신해나가는 형태인 것 같다.  일단 입력을 받고 생각해보려고 했는데입력값이 a->b로가는 비용이 들어오는 형태라서입력을 받으면서 갱신하는 방식이 좀..

https://www.acmicpc.net/problem/2805  풀이 과정일단 문제를 읽어보면 절단기 높이 H를 지정해서 그 단위로 목재를 자르고 떨어져나간 목재를 가져가는 방식이다.그 목재가 M미터가 되도록 최소한 환경을 생각해서 잘라간다는 내용인데...1. 일단 입력값 중 최대값을 찾아2. 그 값을 기준으로 점점 줄이든 늘리든 H를 설정하고3. 잘려나간 나무의 길이가 M이상인지 보는 문제 같다 H를 설정하는게 이 문제의 관건 같은데 나무의 최대 높이가 20억이기 때문에 길이를 하나씩 줄여가면서 보는건 좀 무리인 것 같다.최대 N* M 정도 될 것 같은데 그 값이 만만치가 않다.(근데 그냥 최대 높이가 20이라고 해도 20부터 1까지 1씩 줄여가면서 보는건 좀....노가다스럽긴 하다.. 이런 코드 ..

풀이시뮬레이션 특...일단 문제가 잘 이해가 되지 않고....(한번 읽는 것으로는 잘 이해가 되지 않아서 여러번 읽었다.)구현 자체가 뭔가 할게 많고 조금 복잡한 문제!조건이 뭐가 많길래 패드에 조건을 하나하나 적어가면서 풀었다.  적은 내용 중 풀이 부분에는1. 득표 5% 미만 거르기2. 각 스태프마다 14개의 점수 계산해서 Map에 (점수 : 스태프idx) 저장3. Map 정렬 후 높은점수 부터 chip 주기 (14개의 점수까지만)이 정도를 기록하고 문제 풀기 시작!     일단 입출력을 받고 ArrayList에 저장을 하려고 했는데 입출력을 보니 A, B, C의 알파벳으로 받고 그 다음 득표수로 들어오길래 Candidate 클래스를 만들어서 ArrayList의 형태로 저장을 했다.그리고 N이 0부터..

https://www.acmicpc.net/problem/1730 오늘부터 문제는 올리지 않기로 했다!풀이처음에는 단순한 시뮬레이션 문제인 줄 알았는데 생각보다 복잡했다...처음 풀이는 현재 좌표에만 무늬를 새겨넣고 다음에 갈 곳엔 새기지 않았는데 그렇게 했더니 마지막 위치에 마지막 명령을 시행하지 않는 문제가 생겼다↓ 이전 풀이 방법 ↓더보기package S_1730;// 판화import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; privat..

문제어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다. 입력입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64 이상 1,000,000 이하인 하나의 정수로 주어진다.출력출력은 표준출력..

문제10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35입력첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다.출력첫째 줄에 10진법 수 N을 B진법으로 출력한다.예제 입력 160466175 36예제 출력 1 복사ZZZZZ 풀이진법 변환의 전통적인 방법인 반복문로 계속 나누기....그 왜 어렸을 때 흔히 우리가 2진법으로 바꿀때 몫을 가지고 계속 나누는데 더이상 나누어 지지 않을때까지 하는 그 방법을 코드로 옮기는 방법으로 풀려고 한다. 최..

https://www.acmicpc.net/problem/10448문제삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.[그림]자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.Tn = 1 + 2 + 3 + ... + n = n(n+1)/21796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,4 = T1 + T25 = T1 + T1 + T26 = T2 + T2 or 6 = T310 = T1 + T2 + T3 or 10 = T4이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 ..

문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.입력아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.출력일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경..

문제베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.   시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB106973417383339238.543% 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄..