1, 2일차 리뷰

2019/01/07 - [프로그래밍/알고리즘] - 백준 알고리즘

바로 어제 남겨놓은 글처럼 일단 하루에 한단계씩 할 예정이었으나...

저녁에 밥먹고 일찍 잠들어서 못풀었다...

그래서 일어나자마자 몰아서 2일치를 해버렸다.

문제 풀이(코드) 링크 : https://github.com/gnidoc327/one-day-one-problem

개인적으로는 javascript나 python이 문제풀기 더 편한데

보통 코딩테스트보면 java를 많이 사용하니 그냥 java로 했다.

(근데 살짝 후회 중이다 -> Main class와 public static void main의 반복 ㅂㄷㅂㄷ)

아직까진 거의 복붙하는 코드들이 대부분이라 1~2분도 안되서 풀긴하는데

그나마 2단계 마지막 문제는 좀 생각해야되는 문제라서 다행?이었다.

step 1은 입/출력 받아보기

step 2는 사칙연산 도전하기

그래서 간단했지만 기억에 남는 문제들을 리뷰를 해보자면

---

step 1

7287번 문제

첫 줄에 자신이 맞은 문제의 수, 둘째 줄에 아이디를 출력한다.

설마 진짜 값 비교하나 했는데 

그렇다. 비교해서 채점하더라...

나는 단계별로 문제를 풀다보니 step 1을 풀면 2문제 정도가 step 2와 중복이 되는데

이렇게 목차에서 봤을때 푼 문제수와

마이페이지에서 푼 문제수가 달랐다.(목차는 16문제, 마이페이지는 14문제)

이것만 조심하면 될듯하다

내 풀이 : https://github.com/gnidoc327/one-day-one-problem/blob/master/src/step_by_step/step1/Problem7287/Main.java

11719번

입력 받은 대로 출력하는 프로그램을 작성하시오.

(입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 있을 수도 있다.)

11718번과 다른건 "줄 앞 뒤에 공백이 있을 수 있다."라는 조건이다

계속 쉬운 문제만 하다보니 조건을 제대로 안봐서 계속 틀렸는데 

3번 틀리고 깨달았다 ㅋㅋ

2번 연속 공백이 발생했을때 while 문을 종료하게 만들었다.

처음부터 복잡하게 if문 덕지덕지하지말고 

arrayList에서 이전 값이랑 비교했으면 더 깔끔한 코드가 나왔을텐데

그게 좀 아쉬웠다.

최종 풀이 : https://github.com/gnidoc327/one-day-one-problem/blob/master/src/step_by_step/step1/Problem11719/Main.java

if문 덕지덕지 코드와 diff : https://github.com/gnidoc327/one-day-one-problem/commit/76fd87fe7c916118a7881b57f083de7efa058f8f#diff-90b2707fb9bbfe345916607251542967

---

step 2

2839번

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

그나마 문제다운 문제라고 해야되나

간단하게 표현하면 잔돈 계산하기 문제였다.

즉, 가장 유명한 배낭 문제(0-1 knapsack)와 비슷하다.

(물론 가치를 고려하지 않고 무게만 맞추면 된다는게 쉬웠던 점)

Branch & bound 방식으로 가지치기를 했는데

6kg의 최소 봉지수를 구하는걸 표현하면 아래처럼 된다

[동그라미가 5kg, 네모가 3kg, 오른쪽이 총 합이다.]

1) 가장 적게 봉지를 쓰는 5kg을 최대로 맞춘다.

2) 나머지 무게에서 3kg을 최대치를 구하고 하나씩 빼가며 6kg에 맞춰본다

3) 그래도 없다면 5kg을 하나 빼고 2), 3)을 반복

간단하게 for, if만 쓸 줄 알면 풀 수 있는 문제였다

내 풀이 : https://github.com/gnidoc327/one-day-one-problem/blob/master/src/step_by_step/step2/Problem2839/Main.java

---

2일치 땡겨서 풀어놨으니 오늘은 재밌게 노는걸로...?

심심하면 한 단계 더 풀어놔야지