뚝딱뚝딱

https://softeer.ai/practice/6293

💡 징검다리

• 징검다리 문제는 입력이 3*1000까지 이기 때문에 n^2으로 풀이할 수 있다.
• 계수 정렬을 이용하여 풀이한다.
• 각 돌의 계수를 저장하기 위한 크기가 N인 vector를 생성하고, 값을 1로 초기화해준다.
• 1로 초기화 해주는 이유는, 어떠한 돌을 밟더라도 하나의 돌은 밟은 것이므로 1로 시작한다.
• 0번째를 제외하고, 1번째 돌부터 N-1번째 돌까지 순회하면서, 현재 돌이 이전 돌 보다 큰지를 확인한다.
• 0번째 돌부터 현재 돌의 이전 돌까지 중, 현재 돌보다 작은지 확인하고, 작은 돌들 중에서도 가장 큰 계수를 가져오고, 그 값에 1을 더하여 현재 돌의 계수를 설정하는 방식이다.
• 이런식으로 모든 돌의 계수를 설정하고 나서, 가장 큰 계수를 반환하면 그것이 답이 된다.

• 원리
  예시1
  
  

• n=5일때 위와 같이 돌의 높이가 주어졌다고 하자.
• 3은 시작이고, 이전 돌이 없으며 첫 돌이므로 본인을 포함한 1의 값을 갖는다.
• 2를 보면, 앞의 돌인 3보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 1역시, 앞의 돌인 3,2보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
• 5는 앞의 돌인 3,2,1,4보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
• 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

• 예시2
  
  

• • n=7일때 위와 같이 돌의 높이가 주어졌다고 하자.
  • 1까지 앞의 내용과 같다.
  • 6는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 7은 앞의 돌인 3,2,1,6보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 5는 앞의 돌인 3,2,1,4 보다 크고, 이 중 가장 큰 계수 값이 2 이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

이런식으로 동작하는 것이고, 2줄 for문을 거치기 때문에 n^2의 시간 복잡도가 발생한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N;
  cin>>N;

  vector<int> h(N);//높이를 담을 벡터
  for(int i=0; i<N; i++){
    cin >> h[i];
  }
  
  vector<int> cnt(N,1);//계수를 담을 벡터
  for(int i=1; i<N; i++){
    int cnt_max=0;//이전 계수 중, 돌의 높이가 현재 돌보다 작으면서, 계수가 가장 큰 것을 저장하기 위함
    
    for(int j=0; j<i; j++){
      if(h[i]>h[j]){//이전 돌이 현재 돌보다 작으면
        cnt_max = max(cnt_max, cnt[j]);
      }
    }

    cnt[i]=cnt_max+1;//이전 계수에 현재 돌까지 합쳐서 계수 설정
  }

  cout<<*max_element(cnt.begin(), cnt.end());

   return 0;
}

***참고로 vector의 max값을 반환하기 위해 vector에서 제공하는 max_element() 메서드를 사용했는데, 이 함수는 iterator 즉, 벡터의 요소를 가리키기 때문에, 그 값을 가져오려면 앞에 *를 붙여야 한다. 

소프티어에 있는 lv3 연습 문제 "성적 평균"에 대한 풀이 방법이다.

풀이 날짜는 2023.11.01로, 최근에 소프티어 페이지가 리뉴얼 되었다.

그런데 리뉴얼 후 문제인지, 아니면 이렇게 업데이트 된 것인지 모르겠는데..

어제 다른 문제를 풀 때, 답이 틀리면, 제출 이력에 틀린 답도 뜨고, 왜 틀렸는지(그 문제의 경우 시간초과였음) 표시도 되어있었다.

그런데 오늘 아침부터 풀고 있던 이문제.. 문제 자체에만 틀렸다고 표시되어 있고, 내가 제출한 이력은 전혀 보이지 않는다.

분명 예시 테케도 맞았고, 혹시나 하여 다른 사람들의 풀이랑 내 풀이도 비교해보았는데, 접근 방식이 동일하다.

그런데, 제출만하여 계속 틀렸다고만 뜨고, 제출 이력에는 표시조차 되어 있지 않다. 왜 틀렸는지는 알려줘야지....

거의 20번은 넘게 제출을 한 것 같은데.. 그래서 일단 개발자 톡에 문의를 넣어놓았고, 내 풀이상의 문제일 수 도 있을것 같아 코드도 함께 게시해 놓았다.

부분합 사용

이 문제는 부분합을 사용하면 아주 쉽고 간단하게 풀이할 수 있다.

부분합??

예를 들어서 5명의 학생이 있고, 각각의 점수는 20, 40, 10, 80, 30 이라고 하자.

그러면 크기가 5인 배열에 1명까지 더한 값, 2명까지 더한 값...이렇게 저장하는 것이다.

즉 arr이라는 크기가 5인 배열이 있으면

arr[0] =20

arr[1] = 20+40 = arr[0]+40

arr[2] = 20+40+10 = arr[1]+10

...

이렇게 이전에 저장해둔 값에 새로운 값을 추가로 저장해 총합을 구해 가는 것이다.

배열의 인덱스는 학번과도 같고(문제에서는 1부터 시작하지만, 예시로는 0부터 해도 무방), 만약 1번 학생부터 3번 학생까지의 점수 평균을 구한다면..

3번학생까지의 부분합-0번학생까지의 부분합 = 1번 학생부터 3번학생까지의 점수 합

이기 때문에, 구간이 주어지면 이미 구해진 합을 이용해 구간 합을 쉽게 구할 수 있다.

그리고 1번 학생부터 3번 학생까지 니까 (3-1+1)로 나누어 주면 평균은 바로 구할 수 있다.

따라서 아래와 같은 순서로 진행한다.

1. 학생 수인 N과 구간 수인 K를 먼저 받아서 저장한다.

2. 1부터 i번(1<=i<=N)까지의 학번을 갖는 학생 들의 점수 합을 저장하는 크기가 N+1인 벡터(또는 배열)를 생성한다 => 0번은 0으로 초기화 할 것이다.

3. 입력으로 학생들의 점수를 받을 때, 벡터에 합을 저장해준다.

4. 입력으로 K개의 구간 정보를 입력 받을 때, 앞에서 구한 부분합을 이용해서 평균을 바로 출력한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
  int N,K;
  
  cin>>N>>K;

  vector<double> prefixSum(N+1);

  prefixSum[0]=0;
  
  for(int i=1; i<N+1; i++){
    int S;
    cin>>S;
    prefixSum[i] = prefixSum[i-1]+(double)S;
  }

  int A,B;
  for(int i=1; i<K+1; i++){
    cin>>A>>B;
    printf("%.2f\n", (double)(prefixSum[B]-prefixSum[A-1])/(double)(B-A+1));
  }

  return 0;
}

다른 사람들의 코드랑 비교해보아도, 이상이 없, 예제도 통과하는데, 틀린 이유를 모르겠으나.. 일단은 올려둔다.

예외를 발견한다면 알려주세요!!!