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

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

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

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

 

3-4) 15652번 문제

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

15652번: N과 M (4)

 

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

15652번은 input으로 받은 첫번째 값을 n 두번째 값을 m이라고 할때, 각 row는 m개의 숫자(m개의 index)만을 보여주며 각 index가 1에서 n사이의 숫자를 모두 지나되 자신보다 index가 낮은 경우보다 그 값이 같거나 클 때만 조합되는 경우를 나타냅니다.

    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);
            }
        }
    }

15652번의 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을 해줍니다. (15650번과 차이는 else if문의 = 하나 뿐임!!)

 

조금 더 이해를 돕고자 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 2, index : 2
sb=
1 1
1 2
1 3

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

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

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

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

 

15652번 문제는 여기까지 다루도록 하겠습니다. 15649번에서 15652번까지의 문제 포스팅 모두 마치겠습니다.

 

 

깃주소 :

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

Park1122/Algorithm-Study