[알고리즘풀이]백준 15650: N과 M(2) 스터디 (15649와 함께 보면 좋음)

해당 문제는 15649번과 동일한 점이 많은 문제입니다. 15649번과 다른 점만을 포스팅할 예정이기 때문에 자세히 알고자 하신다면 해당 링크를 확인해주시기 바랍니다.

https://codingjerk-diary.tistory.com/28

[알고리즘풀이]백준 15649 스터디 (15650, 15651, 15652와 input, output동일)

 

3-2) 15650번 문제

문제링크 : https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

15650번의 input과 output은 다음과 같습니다.

 

 

15650번의 규칙은 input으로 받은 첫번째 값을 n 두번째 값을 m이라고 할때, row와 column의 값들 모두 오름차순을 유지하며 각 row는 m개의 column(=index)를 보여주고, 마지막 row의 마지막 column은 n으로 끝나도록 하는 것입니다.

 

    private static void func(String str, int index){
        if(index==m){
            sb.append(str).append("\n");
            return;
        }
        for(int i=1;i<=n;i++) {
            if (str.equals("")){
                func(str+i,index+1);
            }else if(i> Integer.parseInt(str.substring(str.length()-1))){
                func(str+" "+i,index+1);
            }
        }
    }

15650번의 func 함수

 

때문에 i=1부터 n과 같아질 때까지 for문을 돌며 하나의 row에 아직 값이 쌓이지 않았을 경우(str.equals("")) 앞부분에 공백을 두지 않기 위해 func함수로 기존에 쌓아둔 str(= "")에 i를 넣어 str파라미터로 넘겨주고, 다음 index에서 같은 작업을 반복하라고 index+1을 해줍니다. (15649와 동일)

 

그리고 오름차순을 유지하며 column을 쌓기 위해 i의 값(새롭게 추가하고자 하는 값)이 마지막 숫자(String으로 값을 저장했기 때문에 마지막 값(str.length()-1)을 잘라와(str.substring) int형으로 변환한 값(Integer.parseInt))보다 큰 경우에만 func함수로 기존에 쌓아둔 str에 공백(" ")을 추가하고 i를 넣어 str파라미터로 넘겨주고, 다음 index에서 같은 작업을 반복하라고 index+1을 해줍니다.

 

조금 더 이해를 돕고자 func함수의 맨 앞에 출력물을 넣어 확인해본 결과 다음과 같습니다.

(출력물 : System.out.println("str : "+str+", "+"index : "+index+"\n"+"sb=\n"+sb.toString()))

 

=> 3 2를 인풋으로 넣었을 때, 결과는 다음과 같습니다.

str : , index : 0
sb=

str : 1, index : 1
sb=

str : 1 1, index : 2
sb=

str : 1 2, index : 2
sb=
1 1

str : 1 3, index : 2
sb=
1 1
1 2

str : 2, index : 1
sb=
1 1
1 2
1 3

str : 2 1, index : 2
sb=
1 1
1 2
1 3

str : 2 2, index : 2
sb=
1 1
1 2
1 3
2 1

str : 2 3, index : 2
sb=
1 1
1 2
1 3
2 1
2 2

str : 3, index : 1
sb=
1 1
1 2
1 3
2 1
2 2
2 3

str : 3 1, index : 2
sb=
1 1
1 2
1 3
2 1
2 2
2 3

str : 3 2, index : 2
sb=
1 1
1 2
1 3
2 1
2 2
2 3
3 1

str : 3 3, index : 2
sb=
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

<결과>
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

15650번 문제는 여기까지 다루도록 하고 다음에는 15651, 15652문제를 포스팅하도록 하겠습니다.

 

깃 주소:

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ15650.java

Park1122/Algorithm-Study