잡블로그

주어진 일(n)의 모든 날짜(day[0...n-1]의 주식가격이 주어질 때 얻을 수 있는 가장 큰 이익을 찾아라

라고 문제를 정리하고 풀이하였다. 

날의 주가가 있으면 이후 날의 주가가 값이 커야 팔 수 있다. (무조건)

날마다 하나의 주식수를 얻을 수 있으므로. 모든 날의 주식이 있다고 생각하고, 그 중 이익이 최대가 되는 날에 팔아야 하기 때문에

맨 뒤부터 탐색을 하여 값이 더 크면 maxDay_Stock 값을 갱신하고 작은 날이면 현재까지 저장되어 있는 maxDay_Stock - day[i] 의 값을 뺀 만큼이 최대 이익이 된다. 

이 최대 이익을 더하고 답을 출력하면 된다.

간단하게 STL 큐를 사용하여 구현? 하는 문제였다. 

1. 맨위한장을버린다.

2. 1.이후 맨위 한 장을 맨 아래에 깐다. 

3. (1-2) 경우를 다 끝내고 한장이 남았을 때 남는 한장을 출력한다.

이 문제는 BFS로 풀었는데 DP로 풀어야 한다고 하길래 음... 뭐 DP인것같기도 한데 내가 아직 DP에 대한 정확한 개념이 없나부다;;

뭐 문제를 요약하자면, 1,1 부터 m,n 까지 간다 이때 나는 row, col 로 생각하고 매트릭스라 생각했으니 x y 로 받은 값을 뒤집어서 했다 

1,1 ~ m,n 까지 갈 때 가장 벽을 적게 부시고 이동하는 것을 찾는 것이다. 문제의 input으로 '1' 은 벽, '0' 은 뚫린 길이다.

그러니 1을 가장 적게 만나며 최대한 0인 길로 이동해야한다는 얘긴데...

뭐 처음에 생각부터 BFS로 맵을 탐색해야겠다 라고 생각했었고, 이동 중에 가장 짧은 ? 짧다라그래야 하나 아닏;;; 보다 긴 경로를 만나면 긴경로를 작은 값으로 갱신한다.

(큐에넣은자료)이동했을 시에 주변에 (자신)or (자신+1)보다 큰 값이 생기면 각 값으로 갱신한다. (mov 벡터배열을)

큐에 넣고 값을 갱신하는 방식으로 하였다. 

자신 / 자신+1 은 

① 이동 시에 벽이 아닌 것 (0) 

② 이동 시에 벽인 상태 (1)

로 큐에 갱신을 위해 집어 넣는다. 

음.... 위의 방식대로 BFS 탐색을 하며 mov 배열 값을 갱신하며 마지막 값인 mov [m-1][n-1] 을 출력했다.

STL 우선순위큐를 사용하거나 구현하는 문제이다. 

우선순위큐를 어떻게 사용하는지만 알면 풀 수 있는 문제

아 예전에 이 문제보고서 와 이딴 문제 어떻게 풀지 그랬었는데

예전에 생각했던게

이 문제 접근했던 방식은 점 A와 점 B 까지 거리는 어떻게 구하지? 이런 바보 같은 생각을 하나 했었고

이 원들에 대해서 어떻게 판단해야 할까? 라는 생각을 했었다. 

그리고 이번에 문제를 다시보니 아 이렇게 하면 되겠구나 생각이 바로 떠올라서 그렇게 했다. 

일단 두 점이 지나가야하는 원은 어떤 것이 있는 것인가 에 대해서 생각을 했다. 

 점 A에서 점 B로 이동할 때 걸리지 않는 원C은 

① 두 점 다 같은 원C에 들어가 있지 않으며, 

② 두 점 다 같은 원C에 들어가 있어야 한다.

그러면 

③ 두 점 중 한 점만 들어가 있으면 무조건 통과를 해야하는 점이다. 라는 생각을 하였다.

③의 경우만 count++ 해서 결과를 출력하면 되는 문제였다.