kagamimochiを解くためのメモ

atcoderの練習問題を解きました。

問題の概要

N個の餅があって、餅の直径はｄとする。

N個の餅を直径の大きい順に重ねていくと、何段の鏡餅となるかを求める。

N=3、d1, d2, d3はそれぞれ４、３、３の場合、重ねると２段となる。

同じ直径の餅は１段とみなす。

入力の例

入力
３
３
４
３

出力
２

苦戦したこと

同じ直径の餅を１段とみなすためにはどのように処理すればいいのかがわからず苦戦しました。

大きい順にソートして、大きい順に並んだ餅を比較処理する。

ループで比較処理すると、１つ目の餅と２つ目の餅、３番目の餅、...N個目の餅まで比べてしまいカウントがダブってしまうなどと勘違いしていて苦戦しました。２重ループをこれまでの問題でよく使っていたせいで思い込みしていました。

処理の概要

シンプルな１重ループで考えれば普通にすんなりと処理できました。

１回めのループでは１番目の餅と２番めの餅を比べて１番目のほうが大きかったらカウントを増やして次のループへ行く。それ以外（同じ大きさもしくは小さかったら）何もせず次のループに行く。

次のループでは２番めの餅と３番目の餅を比べて、上記と同様の処理を行う。

ということを最後の餅（直径が一番小さい餅）まで繰り返し、最後にカウントを出力するとそれが鏡餅の段数になる。

ループでは次の餅と比べるので、最後に範囲外アクセスによるエラーにならないように、条件を加える。

入力と出力のテストを行って問題なさそうだったので提出し正解できました。

#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
 int N;
 int count = 1;
 cin >> N;
 vector<int> K(N);
 for(int i = 0; i < N; i++){
   cin >> K.at(i);
 }
 sort(K.begin(), K.end());
 reverse(K.begin(), K.end());
 
 for(int i = 0; i < N; i++){
   if(i+1 < N && K.at(i) > K.at(i+1)){
     count++;
   } else {
     continue;
   }
 } 
 cout << count << endl;
 return 0;
}

これでやっと配列の練習問題が終わり次に進めます。

配列のところでだいぶ期間がかかりましたが、基本的な配列とループの扱いに慣れることができて良かったと思います。