행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)
조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.
위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.
1 → 2 → 3 → 8 → 9 → 10 → 15
1 → 2 → 3 → 8 → 13 → 14 → 15
격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.
격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.
행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.
(2) 입력
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.
(3) 출력
주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.
(4) 예제 입력 및 출력
(5) 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class 전화번호목록{
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
//방식 0,0 에서 K까지의 경우의 수 * K에서의 n,m 까지의 경우의 수를 구하면됩니다..
//N은 행 M은 열
StringTokenizer stk = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
int K = Integer.parseInt(stk.nextToken());
//1부터 검사하기위해 +1 해준 값으로 초기화합니다.
int[][] visitCount = new int[M + 1][N + 1];
Point startPoint = new Point(1,1);
Point targetPoint;
int targetX;
int targetY;
int midCount = 1;
int answer = 0;
if(K != 0){
targetX = K % M;
targetY = (K / M) + 1;
if(targetX == 0){
targetX = M;
targetY --;
}
targetPoint = new Point(targetX,targetY);
midCount = DP(startPoint, targetPoint, visitCount);
startPoint = targetPoint;
}
targetX = M;
targetY = N;
targetPoint = new Point(targetX,targetY);
visitCount = new int[M + 1][N + 1];
answer = DP(startPoint, targetPoint, visitCount) * midCount;
bufferedWriter.write(String.valueOf(answer));
bufferedWriter.flush();
bufferedWriter.close();
bufferedReader.close();
}
public static int DP(Point startPoint, Point targetPoint, int[][] visitCount){
// 피라미드 형태로 생각해서 구현하였습니다.
Queue<Point> queue = new LinkedList<>();
visitCount[startPoint.x][startPoint.y] = 1;
queue.add(startPoint);
while(!(queue.isEmpty())){
Point point = queue.poll();
if(!(point.x == startPoint.x && point.y == startPoint.y)){
visitCount[point.x][point.y] = visitCount[point.x - 1][point.y] + visitCount[point.x][point.y - 1];
}
// 범위 설정 오른쪽 또는 아래로 이동하기 때문에 모든 수가 0보다 크다.
if(point.x < targetPoint.x){
Point newPoint = new Point(point.x + 1,point.y);
queue.add(newPoint);
} else {
if(point.y < targetPoint.y){
Point newPoint = new Point(startPoint.x,point.y + 1);
queue.add(newPoint);
}
}
}
return visitCount[targetPoint.x][targetPoint.y];
}
public static class Point{
private int x;
private int y;
public int getX(){
return this.x;
}
public void setX(int x){
this.x = x;
}
public int getY(){
return this.y;
}
public void setY(int y){
this.y = y;
}
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
(2) 입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
(3) 출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
(4) 예제 입력 및 출력
(5) 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class 전화번호목록 {
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
int length = Integer.parseInt(bufferedReader.readLine());
List<String> arrayList = new ArrayList<>();
for (int i = 0; i < length; i++){
int phoneCount = Integer.parseInt(bufferedReader.readLine());
String answer = "YES";
for (int j = 0; j < phoneCount; j++){
arrayList.add(bufferedReader.readLine());
}
Collections.sort(arrayList);
for (int j = 1; j < arrayList.size(); j++){
String currentString = arrayList.get(j);
String preString = arrayList.get(j - 1);
if(currentString.length() > preString.length() && currentString.startsWith(preString)){
answer = "NO";
break;
}
}
bufferedWriter.write(answer + "\n");
arrayList.clear();
}
bufferedWriter.flush();
bufferedWriter.close();
bufferedReader.close();
}
}
그릇을 바닥에 놓았을 때 그 높이는 10cm 이다. 그런데 두 개의 그릇을 같은 방향으로 포개면 그 높이는 5cm만 증가된다. 만일 그릇이 서로 반대방향으로 쌓이면 높이는 그릇만큼, 즉 10cm 늘어난다. 그릇을 괄호 기호로 나타내어 설명해보자. 편의상 그릇이 쌓여지는 방향은 왼쪽에서 오른쪽이라고 가정한다. 그림에서 ‘(’은 그릇이 바닥에 바로 놓인 상태를 나타내며, ‘)’은 그릇이 거꾸로 놓인 상태를 나타낸다.
만일 그릇이 포개진 모양이 ((((와 같다면 전체의 높이는 25cm가 된다. 왜냐하면 처음 바닥에 있는 그릇의 높이가 10cm이고 이후 같은 방향으로 3개의 그릇이 포개져 있으므로 늘어난 높이는 5+5+5=15 이기 때문이다. ()()와 같은 경우라면 그 높이는 10*4=40cm가 된다.
여러분은 입력에 주어진 모양대로 그릇을 쌓을 때 최종의 전체 그릇 높이를 계산해서 출력해야 한다. 즉 처음 입력으로 주어진 각 그릇의 방향은 바꿀 수 없다.
(2) 입력
첫 줄에는 괄호문자로만 이루어진 문자열이 주어진다. 입력 문자열에서 열린 괄호 ‘(’은 바로 놓인 그릇, 닫힌 괄호 ‘)’은 거꾸로 놓인 그릇을 나타난다. 문자열의 길이는 3이상 50 이하이다.
(3) 출력
여러분은 그릇 방향이 괄호 문자로 표시된 문자열을 읽어서 그 최종의 높이를 정수로 출력해야 한다.
(4) 예제 입력 및 출력
(5) 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 그릇 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String string = bufferedReader.readLine();
int answer = 10;
for (int i = 1; i < string.length(); i++){
if (string.charAt(i) == string.charAt(i - 1)){
answer += 5;
}
else{
answer += 10;
}
}
System.out.println(answer);
bufferedReader.close();
}
}
