Programo90 코딩 기록저장소

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

나의 풀이

 문제 자체는 피보나치 수열과 거의 동일하다 단지 피보나치 수열이 바로 이전 두 개의 값을 더하는 것과 다르게, 이전n-1번값과 n-5번 값을 더하는 점. 주어진 도형을 보면 더  쉽게 피보나치 수열과 같은 규칙이 보이는데 정작 테스트실패가 발생한점은 일반식이나 코드의 로직이 아니라 결과값을 int 타입 배열에 저장한 부분이었다. 생각보다 값이 매우 커져서 long배열에 저장해보니 통과

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[101];
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        arr[5] = 2;
        
        for(int i=6; i<101; i++) {
            arr[i] = arr[i-1] + arr[i-5];
        }
        
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            bw.write(arr[num]+"\n");
        }
        bw.flush();
    }
}

문제

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

나의 풀이

 DP문제이기 때문에 각 요소의 값을 누적하며 저장한다는 점이 포인트. 이전에 풀어본 Programmers 정수삼각형 문제와 동일하다. 만약 백준에서 이 문제를 먼저 접했다면 힌트가 더 많이 주어지는 샘. 주어지는 삼각형을 이차 배열로 보고 접근하면 생각보다 간단하다. 아래로 내려올수록 값을 누적하도록 하고, 삼각형의 매 요소마다 받을 수 있는 위에 두 수중에 큰값을 선택하도록 하면 되었다. 복습겸 직접 코딩해보았는데 다행이? 금방 작성했다.

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        int[][] arr = new int[num][num];
        
        StringTokenizer st;
        for(int i=0; i<num; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++) {
                if(i>0&&j==0) {
                    arr[i][0] = Integer.parseInt(st.nextToken()) + arr[i-1][0];
                    continue;
                }
                if(i>0 && j==i) {
                    arr[i][j] = Integer.parseInt(st.nextToken()) + arr[i-1][j-1];
                    continue;
                }
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=2; i<num; i++) {
            for(int j=1; j<=i-1; j++) {
                arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
            }
        }
        
        int max = 0;
        for(int i=0; i<num; i++) {
            max = Math.max(max, arr[num-1][i]);
        }
        
        bw.write(max+"\n");
        bw.flush();
    }
}

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

나의 풀이

 DP문제 답게 훔치는 돈을 더해서 큰 값을 리턴하기로하고 문제풀이를 시작. 반복되는 패턴을 고민해보니 몇 가지 규칙이 보였는데,

 1. 첫번째 집을 털면 마지막 집은 털 수 없다. 집들이 원형으로 연결되기 때문에 첫번째 집과 이웃하게된다.

 2. 두번째 집을 털면 첫번째 집은 털 수 없다. 

 3. n번째 집 다음 n+1번째 집은 털수가 없기 때문에, n+2와 n+3 집중에서 큰돈을 가진 집을 선택해야한다.

이와 같은 규칙은 보였는데 문제는, n+3번째를 선택했을 경우 n+4가 큰값이면 어찌해야 하나 라는 문제였다. 순간 든 생각으로 n+3번째 집 선택을 포기하고 다시 n+2와 n+4를 선택해야하나 싶었는데, 뒤에서 뒤쪽에서 부터 바라보면 문제가 없었다. 다시 말해 n+2번을 기준으로 바라볼때 n번째 집과 n+2번째 집를 선택하는게 나을지, 아니면 n도 n+2도 포기하고 n+1을 선택하는게 나을지를 고민하면 되는 것. 

몇 가지의 DP 문제를 풀면서 보니 진행방향으로 생각하기보다 한차례 앞에서 뒤를 바라보는 식의 문제접근이 해답을 찾기 쉬운경우가 많은 것 같다.

코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int[] arr0 = new int[money.length];
        int[] arr1 = new int[money.length];
        
        arr0[0] = arr0[1] = money[0];
        
        arr1[0] = 0;
        arr1[1] = money[1];
        
        for(int i=2; i<money.length-1; i++) {
            arr0[i] = Math.max(arr0[i-2]+money[i], arr0[i-1]);
            arr1[i] = Math.max(arr1[i-2]+money[i], arr1[i-1]);
        }
        
        
        int leng = money.length-1;
        arr1[leng] = Math.max(arr1[leng-2]+money[leng], arr1[leng-1]);
        
        return Math.max(arr0[leng-1], arr1[leng]);
    }
}

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

나의 풀이

 저번 DP문제와 같이 계산값을 저장하면서 풀면 반복을 줄일 수 있다 라고 생각하고 접근했다. 일단 최단 경로로 이동하기 위해서는 오른쪽으로 가거나, 아래로 가는 선택지만 있다고 보고 각 지점에는 자신까지 올때의 경로의 수를 저장하도록 배열을 만들었다. 여기서 각 지점까지 올 수 있는 경로의 수는 위와 왼쪽 블럭이 막혀있지 않다면 위와 왼쪽 블럭이 가지고 있는 경우의 수를 합한 것으로 구할 수 있었다. 아래 코드로 보면 출발점인 arr[0][0]=1 부터 시작해서 차례로 이동하면서 왼쪽블럭과 위쪽 블럭의 값을 가져와 더한 것. 이번 문제는 DP문제를 몇개 풀어봐서 그런지 생각보다 쉽게 풀려버렸다.

코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] arr = new int[n][m];
        arr[0][0] = 1;
        
        for(int[] point : puddles) {
            arr[point[1]-1][point[0]-1] = -1;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(arr[i][j]<0) continue;
                
                if(i>0 && arr[i-1][j]>0) {
                    arr[i][j] += arr[i-1][j];
                }
                if(j>0 && arr[i][j-1]>0) {
                    arr[i][j] += arr[i][j-1];
                }
                arr[i][j] %= 1000000007;
            }
        }
        
        return arr[n-1][m-1];
    }
}

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

나의 풀이

 DP 카테고리의 문제이기 때문에 당연히 DP 스타일로 풀어야 풀리겠다 생각은 했지만, 일단 DFS 방식으로 문제를 풀어봤다. 코드2 가 그 내용인데 숫자가 많은 케이스는 시간초과로 테스트 통과 실패. DP방식으로 다시 풀어봤다. DP의 가장 큰 특징은 이전에 계산한 내용을 저장이기 때문에 매 차수 계산한 값중에 큰값을 저장하는 방식으로 문제풀이를 접근했다.

 문제 풀이의 핵심으로는 아래 3가지인데,

 1. 삼각형안에서 각 행에 좌우 끝단은 받을 수 있는 숫자가 1가지 뿐이기 때문에 누적되는 값은 고정이 된다.

 2. 좌우끝단이 아닌 자리의 수는 받을 수 있는 수가 2가지 이다. 때문에 매번 자기 위에 숫자 2가지 중 큰 수를 선택하고 주어졌던 값과 더 해준다.

 3. 마지막 행에서 가장 큰 값이 전체 계산 값중에 가장 큰 값이다.

 결과는 테스트 통과. 재귀함수를 통한 문제해결법만 반복하다가 DP를 처음 접했을 땐 참 헷갈렸는데, 공부를 하다보니 상당히 매력적인 방식이라 느껴진다.

코드1 (DP방식)

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int[][] arr = new int[triangle.length][triangle.length];
        arr[0][0] = triangle[0][0];
        for(int i=1; i<arr.length; i++) {
            arr[i][0] = arr[i-1][0] + triangle[i][0];
            arr[i][i] = arr[i-1][i-1] + triangle[i][i];
        }
        
        for(int i=2; i<arr.length; i++) {
            for(int j=1; j<i; j++) {
                arr[i][j] = Math.max(arr[i-1][j-1], arr[i-1][j]) + triangle[i][j];
            }
        }
        
        int answer = 0;
        for(int i=0; i<arr.length; i++) {
            answer = Math.max(answer, arr[arr.length-1][i]);
        }
        
        return answer;
    }
}

코드2 (DFS방식)

import java.util.*;

class Solution {
    static int N;
    static int Max = 0;
    public int solution(int[][] triangle) {
        int acc = 0;
        N = triangle.length;
        acc = triangle[0][0];
        
        recur(1, 0, acc, triangle);
        
        return Max;
    }
    
    static void recur(int depth, int begin, int acc, int[][] triangle) {
        if(depth==N) {
            Max = Math.max(Max, acc);
            return;
        }
        
        for(int i=begin; i<=begin+1; i++) {
            acc += triangle[depth][i];
            recur(depth+1, i, acc, triangle);
            acc -= triangle[depth][i];
        }
    }
}

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

나의 풀이

 DFS 방식으로 문제풀이 접근, 모든 티켓을 소모했을 경우에 리턴하도록 했다. 문제는 전체 티켓을 사용하는 코스가 여러개 발생할 경우(예제2) 알파벳 순서대로 빠른 공항을 먼저 가도록 이기 때문에 배열을 정렬하고 DFS를 시작하기로 했다. 문제 자체는 이전 DFS문제풀이와 사실상 다를게 없기 때문에 금방 코드를 작성했다. 아쉬운 점은 tickets배열을 정렬하는데 있어서 배열이 길어지면 정렬비용이 상당할텐데 이 점을 다른 풀이로 접근해보고 싶었다. 여러 머리를 써봤는데 DFS 방식으로 탐색을 마치고 이전 경로와 비교해서 값이 작은 경로를 선택하도록 하는 방식으로 코드를 짜려니 오히려 복잡해졌다.. 결국 처음 작성한 코드로 풀이를 끝냈다. 

코드

import java.util.*;

class Solution {
    static int N;
    static boolean[] visited;
    public String[] solution(String[][] tickets) {
        N = tickets.length;
        visited = new boolean[tickets.length];
        String[] answer = new String[N+1];
        
        Arrays.sort(tickets, new Comparator<String[]>(){
            public int compare(String[] arr1, String[] arr2) {
                if(arr1[0].compareTo(arr2[0])!=0) {
                    return arr1[0].compareTo(arr2[0]);
                }
                return arr1[1].compareTo(arr2[1]);
            }
            
        });
        
        answer[0] = "ICN";
        dfs(0, tickets, answer);
        
        return answer;
    }
    
    public static boolean dfs(int depth, String[][] tickets, String[] answer) {
        if(depth==N) {
            return true;
        }
        
        for(int i=0; i<tickets.length; i++) {
            if(visited[i] || !answer[depth].equals(tickets[i][0]))
                continue;
            
            visited[i] = true;
            answer[depth+1] = tickets[i][1];
            if(dfs(depth+1,tickets, answer))
                return true;
            visited[i] = false;
        }
        
        return false;
    }
}

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

나의 풀이

 가장 가까운거리 라는 점에서 BFS 방식을 써야겠다 생각을 하고 문제풀이를 시작. 주어진 단어에서 1글자만 다른 경우가 인접 노트라 보고 먼저 그래프를 그려봤다. 이 문제를 DFS로도 풀 수 있겠다 싶었지만, 괜한 반복 없이 답을 구하기엔 BFS가 적합하다 판단하고 코드를 구현했다. BFS에 대해 처음 익힐땐 각 노드마다 인접 노드를 저장하는 방식으로 연습했었는데, 이 문제는 인접노드를 저장할 필요는 없고 그냥 각 노드(단어) 마다 시작하는 단어에서 얼마나 떨어져 있는지와 방문했던 노드인지만 저장하면 됐다. 

코드

import java.util.*;

class Solution {
    class Node {
        String word;
        int leng;
        
        public Node(String word, int leng) {
            this.word = word;
            this.leng = leng;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        Queue<Node> que = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        que.offer(new Node(begin, 0));
        
        while(!que.isEmpty()) {
            Node n = que.poll();
            
            if(n.word.equals(target)) {
                answer = n.leng;
                break;
            }
            
            for(int i=0; i<words.length; i++) {
                if(visited[i] || !checkAd(n.word, words[i])) {
                    continue;
                }
                visited[i] = true;
                que.offer(new Node(words[i], n.leng+1));
            }
        }
        
        return answer;
    }
    
    static boolean checkAd(String w1, String w2) {
        int count = 0;
        for(int i=0; i<w1.length(); i++) {
            if(w1.charAt(i)!=w2.charAt(i))
                count++;
            if(count>1) return false;
        }
        return true;
    }
}

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

문제 풀이

 스도쿠의 규칙은 가로, 세로, 3*3 박스 내에서 같은 값이 없는 1~9 숫자를 넣어서 전체 표를 완성하는 놀이. 여기서 공백이 있는 칸(문제에서는 0)을 가로 세로 박스내에서 체크해서 넣을 수 있는 값을 넣고 다음 빈칸으로 이동하기를 반복 전체 표가 완성되면 출력하도록 했다. DFS 방식으로 접근해서 문제를 풀었는데, 풀고나서 든 생각은 빈칸을 전부 큐에 넣어놓고 하나씩 꺼내가며 가로 세로 3*3박스 내에서 일치하는 값이 없는 확정적인 빈칸에만 값을 넣고, 불확실한 값(여러 값을 넣을 수 있는 경우) 에는 다시 큐에 집에넣는 방식으로 해도 문제가 풀릴거 같다. 어떤 풀이가 더 빠를지는 구현 후 비교해보아야 겠는데, 생각보다 이 코드도 작성하는데 시간이 많이 걸렸어서 큐를 사용한 방식은 해보고 수정하기로..

코드

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

public class Main {
    public static int[][] arr = new int[10][10];
    public static List<Point> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        for(int i=1; i<=9; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==0) {
                    list.add(new Point(i,j));
                }
            }
        }
        
        recur(0);
        
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<10; i++) {
            for(int j=1; j<10; j++) {
                sb.append(arr[i][j]+" ");
            }
            sb.append("\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
    }
    
    public static boolean recur(int idx) {
        if(idx==list.size()) {
            return true;
        }
        Point temp = list.get(idx);
        for(int i=1; i<10; i++) {
            if(!checkMap(temp.y, temp.x,i))
                continue;
            arr[temp.y][temp.x] = i;
            boolean flag = recur(idx+1);
            if(flag) return true;
            arr[temp.y][temp.x] = 0;
        }
        
        return false;
    }
    
    public static boolean checkMap(int y, int x, int num) {
        for(int i =1; i<10; i++) {
            if(arr[y][i]==num || arr[i][x]==num)
                return false;
        }
        
        for(int i = ((y-1)/3)*3+1; i<((y-1)/3)*3+4; i++) {
            for(int j = ((x-1)/3)*3+1; j<((x-1)/3)*3+4; j++) {
                if(arr[i][j]==num)
                    return false;
            }
        }
        return true;
    }  
}

class Point {
    int x;
    int y;
    Point(int y, int x) {
        this.x = x;
        this.y = y;
    }
}