[白俊]2775号:婦人会長-Java(Java)になりたい



今回の問題はマンションのk階n号に何人が住んでいるかです.1階ではなく0階からです.
各階に人が住んでいる戸籍が存在しないことが条件で、自分がb番だとすれば、自分の階下の1番からb番までの人はb番に住むべきだ.

Step 0. 解答コード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class V_President_2275 {
	public static int search_N(int k, int n) {

		int[] apt_1 = new int[n]; // 첫 층
		int[] apt_2 = new int[n]; // 다음 층
		for (int i = 1; i <= n; i++) { // 1층의 1~n명을 전부 넣어줌.
			apt_1[i - 1] = i;
		}
		if (k == 0) {
			return apt_1[n - 1];
		}
		apt_2[0] = 1;
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < n; j++) {
				apt_2[j] = apt_2[j - 1] + apt_1[j];
			}
			apt_1 = apt_2.clone();
		}
		return apt_2[n - 1];
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int k = 0; // 층
		int n = 0; // 호
		for (int i = 0; i < T; i++) {
			k = Integer.parseInt(br.readLine()); // 층
			n = Integer.parseInt(br.readLine()); // 호
			System.out.println(search_N(k, n));
		}

	}

}
これは何の困難もなく解決できる問題だ.1時間ほど探しても正攻法が見つからず私は探してみたが、解く方法はあまり悪くなかったが、やり方が間違っていた人がいた.その中で最も印象的なのは再帰関数を使う方法です.

Step 1. 質問へのアクセス


YXで表現しますYは層数,Xは何番目の格子である.Xの値が0より小さい場合は、10の位置に0を加算します.(001番、103番、1112番...)
問題に近づく前の写真を見せてあげます.

雑然としていますが、特別な関係性はありませんか?だから時計を描いて、赤いペンで注文しました.特別な方法や特別な関係性が見つからなかったので、正攻法で解いた.最初のレイヤには、1~Nの数値が含まれます.各層の最初の格子自体が最初の格子で、値が付加されていないため、次の層の人が入るのが見えます.その後の格子は1階を例に、102号は3人で101号プラス002号の値です.104番を見ると103番6名+004番4名で合計10名です.このようにして問題を解決した.

Step 2. トラブルシューティング


問題を解決するためのsearch N法を作成した.

1.プライマリメソッドは、BufferedReaderを使用して入力を受信します。BufferedReaderを使用しているのでthrowsでIOは除外されています。次に、int T、k、nを使用してテスト繰返し回数、レイヤ、およびアークの値を受信し、for文を使用してテスト繰返し回数Tを使用し、search Nメソッドを呼び出し、印刷する。k,nの値はString形式で受信されるので,int形式に変換する.

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int k = 0; // 층
		int n = 0; // 호
		for (int i = 0; i < T; i++) {
			k = Integer.parseInt(br.readLine()); // 층
			n = Integer.parseInt(br.readLine()); // 호
			System.out.println(search_N(k, n));
		}

2.kとnは、それぞれメインメソッドにレイヤと番号を入力します。

  • 私は2つの配列を生成しました.2つの層に分けられるのは、計算値には現在の層n−1の値と下位層n号の値が必要であるからである.すなわち、必要な値を得るためには、2つのレイヤから値を取得する必要がある.この2つの層から0,1層を求め,1層から2層を求め,2層から3層を求め,所望の層を得た.
  • public static int search_N(int k, int n) {
    
    		int[] apt_1 = new int[n]; // 첫 층
    		int[] apt_2 = new int[n]; // 다음 층
    各配列のサイズはnで、作成されます.また、apt 1アレイは第1層であり、apt 2は次層である.

    3.第1層は1名~n名存在するのでforを用いてapt 1に値を代入した.

    for (int i = 1; i <= n; i++) { // 1층의 1~n명을 전부 넣어줌.
    			apt_1[i - 1] = i;
    		}
    		if (k == 0) {
    			return apt_1[n - 1];
    		}
    		apt_2[0] = 1;
    レイヤが0レイヤの場合、すぐに値が返されます.apt 2の場合、前述したように、すべてのレイヤの最初のセルが1であるため、1が挿入されます.

    4.apt 1は0層の値を提供するので、apt 2も提供する。apt 2は次の層であり、最後に探したk層でもある。まず、apt 2は0層に基づいて1層であり、for文のj変数を使用して各層に値を追加する。最初のセルの値は1なので、次のセルから値を入力します。その後、次の層である第2層の値を求める必要があるため、apt 2をapt 1に深くコピーする。その後,apt 1の1層のデータを用いて深さコピーを行い,2層目のapt 2でデータを更新した。このように1層ずつ上へ進み、所望のk層に到達した後、その層のn番値apt 2[n−1]を返す。

    for (int i = 1; i <= k; i++) {
    			for (int j = 1; j < n; j++) {
    				apt_2[j] = apt_2[j - 1] + apt_1[j];
    			}
    			apt_1 = apt_2.clone();
    		}
    		return apt_2[n - 1];
    	}
    

    Step 3. に感銘を与える


    問題を見ながら考える時間です最後に特別な儀式が存在しないことを知ったが、悪くない時間を懸命に考えた.私が解決した問題ではありませんが、この間、私の関数で解くことができ、私の関数を再確認することができ、問題の処理方法の多様性を高めることができます.
    出典:白駿2775号https://www.acmicpc.net/problem/2775