[BOJ] #3109 빵집, #1339 단어수학

#3109 빵집

문제보러가기

 

문제이해

1열에서부터 마지막 열까지 도착해야한다.

한번 방문한 곳은 다시 방문할 수 없다

오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선을 방문할 수 있다.

해결 방법 고안

1. dfs라고 생각했다. 그 이유는 경로를 찾는거여서 한길을 찾으면 마지막 열에 도착할 수 있는 길을 계속해서 찾아야 했다.

2. 방문 처리가 필요하다. 한번 선택하면 다시 선택할 수 없어서 visited를 true로 놓으면 된다.

3. 백트래킹은 필요없다. 마지막 열에 도착하면 바로 return 한다.

 

코드

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

public class Main {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static int r, c, res;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] deltas = {{-1, 1}, {0, 1}, {1, 1}}; // 위쪽 대각선, 직진, 아래쪽 대각선
    private static boolean flag;

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        r = Integer.parseInt(tokens.nextToken());
        c = Integer.parseInt(tokens.nextToken());
        map = new int[r][c];
        visited = new boolean[r][c];

        // 입력 받아서 .은 0, x는 1로 변환
        for (int i = 0; i < r; i++) {
            String line = input.readLine();
            for (int j = 0; j < c; j++) {
                if (line.charAt(j) == '.') {
                    map[i][j] = 0;
                } else {
                    map[i][j] = 1;
                    visited[i][j] = true;
                }
            }
        }

        for (int i = 0; i < r; i++) {
            flag = false;
            dfs(i, 0);
        }

        System.out.println(res);
    }

    private static void dfs(int x, int y) {
        if (y == c - 1) { // 마지막 열에 도착했다면
            res++;
            flag = true;
            return;
        }

        for (int[] d : deltas) {
            int nx = x + d[0];
            int ny = y + d[1];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && !visited[nx][ny] && map[nx][ny] == 0) {
                visited[nx][ny] = true; // 방문 처리
                dfs(nx, ny);
                if (flag) return; // 경로가 완성되었다면 더 이상 탐색하지 않음
            }
        }
    }
}

 

#1339 단어수학

문제보러가기

 

 

문제 이해

알파벳 A부터 Z까지 나올 수 있다.

최대 10개의 다른 알파벳이 나올 수 있는데 그 알파벳에 0부터 9까지 할당할 수 있다.

N줄이 나오는데 N줄마다 알파벳이 나온다

N줄마다 숫자에 할당되는 것을 구해서 최대합을 구하면 된다.

 

해결 방법 고안

처음에는 순열로 풀었다... 알파벳이 나오면 순열로 각 숫자를 할당하고, 그 중에서 가장 합이 크게 나오는 것을 구했다.

하지만,,, 시간초과가 났다. 이건 그리디 문제였기 때문!! 순열로 풀면 최대 10! *10? 이 정도가 넘게 나오는 것 같다.

그리디로 풀면 의외로(?) 간단한 문제였다.

 

1. 알파벳 배열 26자리를 만들기

2. 알파벳을 받아서 10의 자리 지수로 저장하기

3. 배열 정렬 후 9부터 할당하기

4. 배열의 합을 다 더하기

 

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

public class Main {
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static int alpa[];

	public static void main(String[] args) throws IOException {
		alpa = new int[26];
		int n = Integer.parseInt(input.readLine());
		for(int i=0; i<n; i++){
			String line = input.readLine();
			for(int j=0; j<line.length(); j++){
				if(j == line.length()-1){
					alpa[line.charAt(j)-'A'] +=1;
				}
				else{
					alpa[line.charAt(j)-'A'] += Math.pow(10, line.length()-j-1);
				}

			}
		}
		Arrays.sort(alpa);
		int res=0;
		int num=9;
		for(int i=25; i>=16; i--){
			res += alpa[i]*num --;
		}
		System.out.println(res);

	}
}