Junnnho

BOJ : https://www.acmicpc.net/problem/1744

github : https://github.com/junho0956/Algorithm/blob/master/1744/1744/%EC%86%8C%EC%8A%A4.cpp

수 묶기 문제는 일정 수열이 주어졌을 때 이 수열의 합을 최대한으로 만드는 문제입니다. 

여기서는 임의의 숫자를 다른 숫자와 묶는게 가능한데 이 묶기가 * 곱하기입니다.

예를 들어 0 1 2 4 3 5 라는 수가 있고 이를 모두 더하면 15가 됩니다.

하지만 (4,5) (2,3) 을 묶으면(곱하면) 0 1 (2*3) (4*5) 가 되고 이를 합하면 27이 됩니다.

저는 이런식으로 문제를 접근했습니다.

정수가 나올 수 있는 범위는 -10000~10000 이므로 일단 음수가 나올 수 있음에 주의해야합니다.

마찬가지로 0도 나올 수 있다는거죠!

그럼 양수는 최대한 높은 것끼리 곱해주는게 총 합에 이득일 것이고,

음수는 최대한 작은 것 끼리 곱해주는게 총 합에 이득일 것입니다.

여기서 또 뭘 생각해보았냐면

0과 1에 주의하는 것입니다.

1보다 큰 양수는 0과 곱해지면 무조건 손해를 보고 1과 곱해져도 무조건 손해입니다.

1 2 가 있다면 1*2 를 하는 것은 손해니까요

그리고, 음수는 분명 짝을 지어서 서로 곱하는게 무조건 이득입니다.

근데, 짝을 못찾는 음수가 남을 수 있으니, 이는 0과 곱해서 그냥 0으로 만들어버리는 것입니다.

이 경우는 단 1가지밖에 존재할 수 없습니다. 음수는 남거나 안남거나 둘 중 하나니까요

이 정도만 고려하니 문제를 해결할 수 있었습니다.

BOJ : https://www.acmicpc.net/problem/11399

github : https://github.com/junho0956/Algorithm/blob/master/11399/11399/%EC%86%8C%EC%8A%A4.cpp

현재 사람이 앞사람이 돈을 인출하는데 걸리는시간을 최소화하기 위해서는 앞사람이 인출하는 시간을 줄이면 된다.

==> ATM 인출 시간을 가장 작게 줄이는 방법은 정렬을 해주는 것으로 해결할 수 있다.

BOJ : https://www.acmicpc.net/problem/1931

github : https://github.com/junho0956/Algorithm/blob/master/1931/1931/%EC%86%8C%EC%8A%A4.cpp

회의실을 최대한 많이 사용하기 위해서는 회의의 시작시간이나 회의시간 이 중요한게 아니고

회의가 언제 끝냐느냐가 가장 중요합니다.

회의가 빨리 끝나는 순으로 정렬하여서 가능한 모든 회의를 진행하면 이게 최대의 횟수가 됩니다.

BOJ : https://www.acmicpc.net/problem/1783

github : https://github.com/junho0956/Algorithm/blob/master/1783/1783/%EC%86%8C%EC%8A%A4.cpp

처음에는 진짜 이걸 어떻게 푸나 싶었다.

범위도 크고 진짜 탐색할수도 없고

그래서 1~4번 규칙을 이용해서 몆가지 예시를 만들어가보니 규칙이 보였다.

만약 N 이 1이면 1 2 3 4 조건을 사용할수가 없다. => 1개

만약 N 이 2이면 1 4 조건은 사용못하지만 2 3 은 사용할수있다.  

중요한 것은 만약, 이동 횟수가 4번 이상인 경우에는 위의 이동 방법을 각각 한 번 이상 이용해야 한다. 는 제약이다.

그래서 M 의 길이에 따라 최대 4개가 될 수 있다.

만약 N 이 3이상이라면 1 2 3 4 조건을 모두 사용할 수 있게 된다.

이때는 최대한 많은 방문을 해야한다고 했으니, 규칙상 가로를 2칸이동하는 것 보다는 세로를 2칸씩 이동하는 것이

더 많은 방문을 할 수 있다.

그러므로 2 3 조건을 1번씩만 사용한다면 1 4 조건으로만 계속 1줄씩 채워나갈수 있다

M 의 길이에 주의해서 2 3 조건을 1번씩만 사용하니 방문못하는 경우는 단 2줄밖에 없게 된다.