[2021 동계 모각코] 4회차 회고록

---

4회차(2022.01.28 15:00~18:00)

4회차 목표

---

회의를 통해

모각코 시간에 모여서 앱 개발을 하는 것보다, 이 시간에는 각자 공부를 하고,

더 충분한 시간을 가지고 앱 개발을 위해 노력하는 것이 좋다고 판단하였다.

 

1. 알고리즘 문제해결전략

서론 부분인

- 코딩과 디버깅에 관하여

https://www.notion.so/8c7a3c0e6f2a4483b9155b73c237f4e2

- 알고리즘의 시간 복잡도 분석

https://www.notion.so/7bcc0e2326a84ba9aee5b25d90114b0a

부분에 대해 읽고 정리하였다.

 

2. 백준 2문제 이상 풀기

1) 1783 병든 나이트

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

위의 경로로만 움직일 수 있는 말을 이용해 방문할 수 있는 최대 칸의 개수를 구하는 문제이다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        String[] s = input.split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        int result=1;
        if(n==1) {
            result = 1;
        } else if(n==2) {
            result += Math.min(3, (m-1)/2);
        } else {
            if(m<7) {
                result += Math.min(3, m-1);
            } else {
                result += m-3;
            }
        }

        System.out.println(result);
    }
}

먼저 n==1인 경우,

더이상 움직일 수 없으므로 결과는 1

 

n==2인 경우,

위, 아래로 1칸만 움직일 수 있으므로 무조건 오른쪽으로 2칸 이동해야한다.

따라서, 가로 길이 m에서 현재 위치가 1이므로 m-1을 2로 나눈 몫이 이동할 수 있는 수가 되는데,

이 때 이동할 수 있는 수가 4보다 적어야 하므로 3과 (m-1)/2 중 더 작은 값을 result에 더한다.

 

n이 1, 2가 아니고, m이 7보다 작은 경우,

4가지 경우에서 오른쪽으로 움직이는 칸을 모두 더해보면 6인데,

처음 시작 위치가 1이므로 1+6 = 7이 된다.

7보다 작은 경우는 이동 횟수가 4번보다 적음을 의미하므로, 3과 m-1 중 작은 값을 result에 더한다.

 

그렇지 않은 경우,

4가지 이동 방법을 모두 사용하면 오른쪽으로 6칸 이동하고, 이렇게 될 경우 이동 횟수는 4가 되며,

이후에는 오른쪽으로 1칸 이동하는 것이 방문 칸이 최대가 될 수 있도록 하는 경우이므로

가로 길이 m-1 에서 6을 빼고 4를 더한 m-1-6+4 = m-3이 된다.

 

2) 1699 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

주어진 자연수를 제곱수의 합으로 나타낼 때 제곱수 항의 최소 개수를 구하는 문제이다.

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int n = Integer.parseInt(input);

        int[] result = new int[n+1];

        for(int i=1;i<=n;i++) {
            result[i] = i;
            for(int j=1;j*j<=i;j++) {
                if(result[i]>result[i-j*j]+1) {
                    result[i] = result[i-j*j]+1;
                }
            }
        }
        System.out.println(result[n]);
    }
}

dp를 이용하여 문제를 해결하였다.

반복문을 이용하여 result[i]에 i를 대입해두고,

j=1부터 j의 제곱이 i보다 작거나 같을 때까지 j를 1씩 증가시키며

result[i]가 result[i-j*j]+1보다 크다면, result[i]에 해당 값을 대입하도록 하였다.

 

result[i-j*j]가 의미하는 것은 i를 j의 제곱과 i-j*j로 표현함을 의미한다.

 

3) 2331 반복수열

https://www.acmicpc.net/problem/2331

2331번: 반복수열

반복되는 부분을 제외했을 때 수열에 남는 수의 개수를 출력한다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        String[] s = input.split(" ");
        int a = Integer.parseInt(s[0]);
        int p = Integer.parseInt(s[1]);

        List<Integer> numlist = new ArrayList<>();

        String tmp = s[0];

        numlist.add(a);
        boolean stop = false;
        while(!stop) {
            int result=0;

            char[] arr= tmp.toCharArray();
            for(int i=0;i<arr.length;i++) {
                int num = arr[i] - '0';
                result += Math.pow(num, p);
            }

            for(int i=0;i<numlist.size();i++) {
                if(numlist.get(i)==result) {
                    System.out.println(i);
                    stop=true;
                }

            }

            numlist.add(result);
            tmp = Integer.toString(result);
        }
    }
}

ArrayList를 만들어 입력 받는 수들을 list에 추가하는데, 

처음 입력 받은 수를 문자로 바꾸어 반복문을 이용해 각각 숫자로 바꾼 뒤, p제곱 하여 result에 더해준다.

list에 해당 결과가 존재하는지 찾고, 존재한다면 인덱스 i를 출력한다.

numlist에 result를 추가하고,

tmp에는 result를 String으로 변환한 값을 대입해주고,

 

stop 값에 따라 반복문을 계속할지, 멈출지 정한다.

---

3시간동안 앉아서 공부를 해야 했는데,

좋은 습관을 위한 한걸음이었던 것 같다.

친구들이 어떤 공부를 하는지도 알 수 있었고, 열심히 하는데 좋은 동기가 되었다.