WantAirpod

www.acmicpc.net/problem/14888

문제해설

• 숫자 사이사이에 연산자를 끼워넣는 느낌.
• 그러기 위해서는 DFS로 구현
  • ex) 연산자가 1 0 1 0 이라고 가정하고 List에 두가지 경우 0, 2와 2, 0경우를 재귀로 돌린다.
  • 0, 2의 경우 3 [0] 4 [2] 5 -->0은 더하기, 2는 곱하기 max or min을 구한다.
  • 2, 0의 경우 3 [2] 4 [0] 5 --> "

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[11];
int vi[4];
int ar[4];
int resmax = -1000000001, resmin = 1000000001, n;
vector<int> v;

void input()
{
   cin >> n;
   for (int i = 0; i < n; i++)
      cin >> map[i];
   for (int i = 0; i < 4; i++)
      cin >> ar[i];
}

void pro(int ct)
{
   if (ct == n - 1)
   {
      int S = map[0];
      for (int i = 0; i < v.size(); i++)
      {
         if (v[i] == 0)
            S += map[i + 1];
         else if (v[i] == 1)
            S -= map[i + 1];
         else if (v[i] == 2)
            S *= map[i + 1];
         else if (v[i] == 3)
            S /= map[i + 1];
      }
      resmax = max(resmax, S);
      resmin = min(resmin, S);
      return;
   }

   for (int w = 0; w < 4; w++)
   {
      if (ar[w] == 0)
         continue;
      if (vi[w] < ar[w])
      {
         vi[w]++;
         v.push_back(w);
         pro(ct + 1);
         v.pop_back();
         vi[w]--;
      }
   }
}

int main()
{
   input();
   pro(0);
   cout << resmax << endl << resmin << endl;
   return 0;
}

Java

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

public class Main {
	static int N;
	static int numbers[];
	static int count[] = new int[4];
	static int visited[];
	static ArrayList<Integer> comb = new ArrayList<Integer>();
	static int max = -1000000001;
	static int min = 1000000001;

	// static int result_max;
	// static int result_min;
	static void pro(int ct) {
		if (ct == N - 1) {
			// System.out.println(comb);
			int sum = numbers[0];
			for (int i = 0; i < comb.size(); i++) {
				if (comb.get(i) == 0) {
					sum += numbers[i + 1];
				} else if (comb.get(i) == 1) {
					sum -= numbers[i + 1];
				} else if (comb.get(i) == 2) {
					sum *= numbers[i + 1];
				} else if (comb.get(i) == 3) {
					sum /= numbers[i + 1];
				}
			}
			// System.out.println(sum);
			max = Math.max(sum, max);
			min = Math.min(sum, min);

		}
		for (int i = 0; i < 4; i++) {
			if (count[i] == 0)
				continue;
			if (visited[i] != count[i]) {
				visited[i]++;
				comb.add(i);
				pro(ct + 1);
				// System.out.println(comb);
				comb.remove(comb.size() - 1);
				visited[i]--;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		numbers = new int[N];
		// 0: + 1:- 2: x 3: /
		visited = new int[4];
		Arrays.fill(visited, 0);
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		input = br.readLine();
		st = new StringTokenizer(input);
		for (int i = 0; i < 4; i++) {
			count[i] = Integer.parseInt(st.nextToken());
		}
		pro(0);
		System.out.println(max);
		System.out.println(min);
	}

}

www.acmicpc.net/problem/9536

문제해설

• 알고리즘 자체보다는 문자열 문제
• what does the fox say? 가 나올 때 문자열을 종료시켜주는 것
• StringToken 잘 쓰기. -->
  

wantairpod.tistory.com/86

Java

package Z_ShinHanCard_Prepare;
import java.util.*;
import java.io.*;
/*
 * 1
toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot
dog goes woof
fish goes blub
elephant goes toot
seal goes ow
what does the fox say?
 * */
public class D4백준9536_여우는어떻게울지 
{
	

	public static void main(String[] args) throws Exception
	{	String question="what does the fox say?";
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		int T = Integer.parseInt(input);
		String s[]= new String[T];
		Vector<String> animals = new Vector<String>();
		StringTokenizer st;
		for(int i = 0 ; i <T ; i++)
		{
			animals.clear();
			input = br.readLine();
			s[i]=input; //동물소리 입력받음
			for(int  j= 0 ; j<100 ; j++)
			{
				String temp =br.readLine();
				if(temp.equals(question))
				{
					break;
				}
				st =new StringTokenizer(temp," ");
				int tempCout =st.countTokens();
						
				for(int w= 0 ; w<st.countTokens() ;j++) {
					if(st.nextToken().equals("goes"))
					{
						animals.add(st.nextToken());
					}
				} 
			}
			
			st=new StringTokenizer(s[i]," "); 	
			while (st.hasMoreTokens()) 
			{
				int check=0;
				String animal = st.nextToken();
				
				for (int k=0; k<animals.size(); k++) 
				{
					if (animal.equals(animals.get(k)))
					{
						check=1;
						break;
					}
					else check=0;
				}
				if (check==0) {
					System.out.print(animal+ " ");
				}
			}
		} 
	}

}

• StringTokenizer 클래스는 문자열을 우리가 지정한 구분자로 문자열을 쪼개주는 클래스입니다. 그렇게 쪼개어진 문자열을 우리는 토큰(token)이라고 부릅니다.
• java.util.StringTokenizer
  • int countTokens()
    • 남아 있는 token 반환
  • boolean hasMoreElemets()
    • 다음 토큰이 있으면 true 없으면 false 반환
  • String nextToken()
    • 다음의 토큰을 반환
• 코드

package Z_ShinHanCard_Prepare;
import java.util.*;
import java.io.*;
public class D4StringTokenizer연습 
{

	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		//String totalStr ="toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot";
		String totalStr ="hello world hi world";
		StringTokenizer st = new StringTokenizer(totalStr);
		System.out.println(st);
		System.out.println();
		
		
		System.out.println("total tokens : " + st.countTokens());
		System.out.println();
		
		while(st.hasMoreTokens())
		{
			System.out.println(st.nextToken());
		}
		
		System.out.println("total tokens : " + st.countTokens());
		
		
	}

}

결과

CASE1

• 붙어있는 경우

• N 첫줄을 parse해준다.
• N을 이용해서 루프를 돈다.
• i는 한줄씩->input=br.readLine();
• j는 한글자씩-> arr[i][j] = input.charAt(j) - '0';
  • br.readLine()은 한줄을 String으로 받기 때문에 숫자로 바꿔주기 위해서 -'0'을 해준다.

		BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
		String input= br.readLine();
		N = Integer.parseInt(input);
		house = new int [N][N];
		visited = new boolean [N][N];
		//Arrays.fill(visited, false);
		for(int i = 0 ; i < N; i++)
		{
			input = br.readLine();
			for(int j =0 ; j < N ; j++)
			{
				int tempNum = input.charAt(j);
				house[i][j] = input.charAt(j) -'0'; 
			}
		}

CASE2

• 떨어져 있는 경우

• StringTokenizer 를 사용한다. 
• br.readLine(=String) 은 같다. 하지만 한 줄에서 띄어쓰기전까지만 짜른다.
• ex) 30 50
  • StringTokenizer st =new StringTokeizer(input); //input은 한 줄 
  • int first = Interger.parseInt(st.nextToken()); // 한줄에서 띄어쓰기 전까지 first -> 30
  • int second = Integer.parseInt(st.nextToken()); // 50

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc =0; tc<T; tc++)
		{
			inin();
			L=Integer.parseInt(br.readLine()); //L*L 
			visit =new boolean[L][L];
			for (boolean row[]: visit) {
				Arrays.fill(row,  false);
			} //초기화시킴
			String input = br.readLine();  // 0,0
			StringTokenizer st= new StringTokenizer(input);

			int sx =Integer.parseInt(st.nextToken()); 
			int sy =Integer.parseInt(st.nextToken()); 
			input = br.readLine();  // 0,0
			st= new StringTokenizer(input);
			int ex =Integer.parseInt(st.nextToken());
			int ey =Integer.parseInt(st.nextToken());
         }

www.acmicpc.net/problem/1654

문제풀이

• 이분 탐색으로 구현
• 정확하게 이분탐색을 알아야만 풀 수있음
• int형이아닌 long으로 받는 것이 중요 (N=1,000,000)
• 길이는 자연수라고 했으므로 min 값을 1로 잡는 것이 중요(상식적으로 길이가 0인 선은 없는 것임)

Java

package Z_ShinHanCard_Prepare;
/*
 * 4 11
   802
   743
   457
   539
 * */
import java.io.*;
import java.util.*;
public class D3백준_랜선짜르기_이분탐색 {
	static ArrayList<Integer> arr  = new ArrayList<Integer>();
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		for(int i =0 ; i <R ; i++)
		{
			input = br.readLine();
			int temp = Integer.parseInt(input); 
			arr.add(temp);
		}
		Collections.sort(arr);
		//arr : 457 539 743 802 
		long max = arr.get(R-1); 
		long min = 1; //자연수라서 1
		long middle =0; 
		
		while(max>=min) //이분탐색
		{
			middle = (max+min)/ 2;
			long allcount =0;
			for(int i =0  ; i <arr.size(); i++)
			{
				allcount += arr.get(i) / middle; 
			}
			 
			if(allcount >= C) 
			{
				min = middle +1;
			}else if(allcount <C )
			{
				max=middle -1;
			}
				
		}
		
		System.out.println(max);
		 
		
		// TODO Auto-generated method stub

	}

}

www.acmicpc.net/problem/9012

문제풀이

• '('은 Stack에 계속 담음
• ')'은 Stack에 '('로 끝날때 '(' 을 pop 시켜준다.
  • 만약 Stack 비어있으면 break

Java

package Z_ShinHanCard_Prepare;
/*
 *  6
	(())())
	(((()())()
	(()())((()))
	((()()(()))(((())))()
	()()()()(()()())()
	(()((())()(
*/
import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class D3백준9012_괄호_stack {
	static int T,n,m;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T= Integer.parseInt(br.readLine());
		Stack<Character> stack = new Stack<Character>();
		boolean check = true;
		for(int i = 0 ; i < T ; i++)
		{
			String input = br.readLine();
			stack.clear();
			for(int j = 0 ; j < input.length() ; j++)
			{
				check =true;
				char temp = input.charAt(j);
				if(temp == '(')
				{
					stack.push(temp);
				}else if(temp ==')')
				{
					if(stack.isEmpty())
					{
						check = false;
						break;
					}
					stack.pop();
					
				}
				 
			}
			if(check ==true && stack.isEmpty())
				System.out.println("YES");
			else
				System.out.println("NO");
			
 		}
	}
}

www.acmicpc.net/problem/7562

문제풀이

• 이동 dx, dy를 잘 체크해준다.
• 이동 할 때마다 체크 및 +1 씩 해준다.
• 도착 지점이면 바로 break;로 나온다.

c++

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
/*
8
0 0
7 0 */

using namespace std;
int k, sa, sb, ea, eb;
int visit[1000][1000];
const int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 

int ans;

struct Point
{
	int x;
	int y;
	int num;
};
queue <Point> q;
vector<int> answer;

void input()
{
	cin >> k;
	cin >> sa >> sb;
	cin >> ea >> eb; 
}
int solve()
{
	visit[sa][sb] = 1;
	q.push({ sa, sb, 0 });
	while (!q.empty())
	{
		Point pp = q.front();
		int x = pp.x;
		int y = pp.y;
		int nn = pp.num;
		q.pop();
	

		for (int w = 0; w< 8; w++)
		{
			int nx = x + dx[w];
			int ny = y + dy[w];
			int nnn = nn + 1;
			if (nx == ea && ny == eb)
			{
				return nnn;
			}
			if (nx >= k || ny >= k || nx < 0 || ny < 0)
			{
				continue;
			}
			if (visit[nx][ny] == 1)
				continue;
			if (visit[nx][ny] == 0)
			{
				visit[nx][ny] = 1;
				q.push({ nx, ny, nnn  });
			}


		}
	}
	return 0;
}
void Init()
{

	queue <Point> q;
	memset(visit, 0, sizeof(visit));
	ans = 0; 
 
}
int main()
{
	int t; cin >> t;
	for (int i = 0; i < t; i++)
	{
		input();
		Init();
		int anss = solve();
		cout << anss << endl;
	}


	return 0;
}

Java

package Z_J_Code;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.*;
class Location12 {
	int x;
	int y;
	int level;
	public Location12 (int x, int y, int level) {
		this.x= x;
		this.y=y;
		this.level= level;
	}
}
public class Main3 {
	

	static int L;//체스판 크기
	//static int board[][];
	static int visited[][];
	//static Stack<Location> stk= new Stack<Location>();
	static Queue<Location12> que = new LinkedList<Location12>();
	static int dir_x [] = {-1, -2,-2, -1, 1, 2, 2, 1};
	static int dir_y []= {-2, -1,1, 2, 2, 1,-1, -2};
	static int count=0;
	
	
	static int search (int x, int y, int endX, int endY) {
		//stk.push(new Location(x,y)); 
		que.add(new Location12(x,y,0));
		while (!que.isEmpty()) {
			Location12 current =que.poll();
			//if (current.x==endX && current.y==endY) return;
			//count++;
			//System.out.println("curent:"+ current.x+ ","+ current.y+ ","+ current.level);
			for (int i=0; i<dir_x.length; i++) {
				int nextX= current.x+dir_x[i];
				int nextY= current.y+dir_y[i];
				int level= current.level+1;
				if (nextX==endX && nextY==endY) {
					//System.out.println(nextX+", "+ nextY);
					return level;
				}
				if (nextX>=0 && nextX<L && nextY>=0 && nextY<L && visited[nextX][nextY]==0) {
					//System.out.println(nextX+", "+ nextY+ ","+ level);
					visited[nextX][nextY]=1;
					que.add(new Location12 (nextX, nextY,level));
					//count++;
					
				}
			}
		}
		return 0;
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int tc =Integer.parseInt(br.readLine()); //테케 갯수
		for (int i=0; i<tc; i++) {
			que.clear();
			count=0;
			L= Integer.parseInt(br.readLine()); //체스판 크기
			
			//board = new int [L][L];
			visited = new int [L][L];
			for (int row[]: visited) {
				Arrays.fill(row,  0);
			} //초기화시킴
			String input= br.readLine();
			StringTokenizer st= new StringTokenizer(input);
			int startX= Integer.parseInt(st.nextToken()); 
			int startY= Integer.parseInt(st.nextToken());
			input = br.readLine();
			st= new StringTokenizer(input);
			
			int endX= Integer.parseInt(st.nextToken()); 
			int endY= Integer.parseInt(st.nextToken()); 
			
			if (startX==endX && startY==endY) System.out.println(0);
			else {
			visited[startX][startY]=1;
			System.out.println(search(startX, startY, endX, endY));
			}
			//System.out.println(count);
		}
	}

}

www.acmicpc.net/problem/2644

문제풀이

• 노드 짜는 문제...!
• 노드 (부모, 자식) 중요 
  • 조상, 자식 개념으로 생각하는게 맞을듯...
  • 출발 부터 조상은 여러명이 될 수있음.
• 각각 서로 같은 조상을 만났을 때
  • 직속 : 본인(person1)과 목적지(person2)가 서로 할아버지->아버지->나 이런 관계 일때 ex) 7-2 관계
  • 직속으로 만났을 땐 해당 인덱스 +1 해준다. 
  • 직속이 아닐 경우 각각의 인덱스에서 +2 해준다. +2 란 가는 경로를 다 더해주는 느낌이다.
• 입력 받아오는 것 노드 연결 까지 입력 코테에서는 가장 좋은 문제

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct aaa
{
	int p;
	vector<int> v;
};
aaa ar[10001];
int num1,num2;
int ans;
int cnt;

void input()
{
	int numSize;
	cin >> numSize;
	for(int i =0 ; i < numSize; i++)
	{
		int a, b;
		cin >> a >> b; //1,2 
		ar[a].v.push_back(b);
		ar[b].p = a;
	}

}

void dfs(int n)
{
	int temp;
	temp = ar[n].p;
	if (n == ans || ans ==-1 ||temp ==0)
	{
		return;
	}
	cnt++;
	
	
	if (temp != 0)
		dfs(temp);
	else
		return;
}
void solve()
{
	vector<int> vv[2];
	//ROOT 이면..
	if (ar[num1].p == 0 && ar[num1].v.size() == 0)
		return;
	if (ar[num2].p == 0 && ar[num2].v.size() == 0)
		return;
	vv[0].push_back(num1);
	int x =num1;
	while (1)
	{
		if (ar[x].p == 0) //즉 부모가 없으면 
		{
			//vv[0].push_back(0);//부모삽입
			break;
		}
		vv[0].push_back(ar[x].p);//부모삽입
		x = ar[x].p;  // x를 부모로 바꿈 그 부모를 찾기위해  따라서 v[1]에는 부모들이 쌓임 
	}
	vv[1].push_back(num2);
	int y =num2 ;
	while (1)
	{
		if (ar[y].p == 0)
		{
			break;
		}
		vv[1].push_back(ar[y].p); //두번째숫자의 부모들 넣음
		y = ar[y].p; //부모 체인지  맨끝까지 올라감 
		//즉 3,7은 각자의 맨끝인 1까지 삽입 
	}
	
	
	

	for (int i = 0; i < vv[0].size(); i++)
	{
		
		bool flag = false;
		int res;
		for (int j = 0; j< vv[1].size(); j++)
		{
			if (vv[0][i] == vv[1][j])
			{
				res = vv[0][i];
				flag = true;
				break;
			}
			/*else 
			{
				ans = -1; //조상이 같지 않음! 남남
			}*/
			
		}

	//	sort(vv[0].rbegin(), vv[0].rend());
//		sort(vv[1].rbegin(), vv[1].rend());

		if (flag == true) //조상을 찾았다면!
		{
			//추가
			for (int w = 0; w < vv[0].size(); w++)
			{
				cnt++;
				if (vv[0][w] == res)
				{
					break;
				} 
			}
			for (int w = 0; w < vv[1].size(); w++)
			{
				cnt++;
				if (vv[1][w] == res)
				{
					break;
				}
			}
			cnt -= 2;
			break;
		}
	}
 
}

int main()
{
	int tm;
	cin >> tm;
	cin >> num1 >> num2;
	input();
	solve();
	if (cnt == 0)
	{
		cnt = -1;
	}
	cout << cnt << endl;
	return 0;
}

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node_Family
{
	int parent;
	ArrayList<Integer> child;
	int level;
	public Node_Family(int parent, ArrayList<Integer> child, int level) {
		super();
		this.parent = parent;
		this.child = child;
		this.level = level;
	}
	 
}

public class D2백준2644_촌수계산_DFSBFS_노드 {
	static Node_Family family[] =new Node_Family[101];
	static int answer ;
	static void solve(int person, int person2)
	{
		int x = person;  //7 
		ArrayList<Integer> [] arr= new ArrayList[2];
		Queue<Integer>que= new LinkedList<Integer>();
		for (int i=0; i<2;i++) 
		{
			arr[i]= new ArrayList<Integer>();
		}
		//node1의 부모탐색 즉 7의 부모탐색 
		while(true)
		{
			//부모가 더이상없다면 끝내 처음에 0으로 생성함.
			if(family[x].parent==0)
				break;
			//아니면 arr[0]리스트에 부모들을 다 더해준다. 아버지+할아버지
			arr[0].add(family[x].parent);
			x= family[x].parent; 
		}
		//숫자 3에 조상 다 구하기
		x= person2;
		while(true)
		{
			if(family[x].parent==0)
				break;
			arr[1].add(family[x].parent);
			x= family[x].parent;
		}
		//첫놈의 조상 중에 둘째 놈이 있다면 ?
		if(arr[0].contains(person2))
		{
			// [0][0] 있다면 1촌 [0][1]에 있다면 2촌
			answer= arr[0].indexOf(person2)+1;
		}else if (arr[1].contains(person))
			answer =arr[1].indexOf(person)+1;
		else
		{
			boolean flag = false;
			for(int i = 0 ; i<arr[0].size();i++)
			{	for(int j = 0 ; j < arr[1].size(); j++)
				{
					if(arr[0].get(i)==arr[1].get(j) )
					{
						answer = i+j +2;
						flag=true;
						break;
					}
				}
				if(flag)
					break;
			}
			
			if(!flag)
			{
				answer = -1; 
			}
		}
		
	}
	
	
	public static void main(String[] args) throws Exception 
	{
		/*
		 *  9 //전체사람수 9명 
			7 3 //7과 3은?
			7   //관계 7
			1 2
			1 3
			2 7
			2 8
			2 9
			4 5
			4 6
		 * */
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int m= Integer.parseInt(br.readLine()); //총 인원 : 9
		String input= br.readLine(); //누구누구?  7,3 
		StringTokenizer st= new StringTokenizer(input);
		int person= Integer.parseInt(st.nextToken()); //7
		int person2= Integer.parseInt(st.nextToken());//3
		// TODO Auto-generated method stub
		int e= Integer.parseInt(br.readLine()); //7번 !
		for(int i = 0 ; i<family.length;i++)
		{
			family[i] =new Node_Family(0,new ArrayList<Integer>(), 0);
		}
		for(int i =0 ; i <e ; i++)
		{
			input =br.readLine();//1,2 -> 1,3 
			st= new StringTokenizer(input);
			int node1= Integer.parseInt(st.nextToken()); //1
			int node2=Integer.parseInt(st.nextToken()); //2
			//1의 자식 2라는 뜻 1의 자식이 여러명 일수 있으니 array리스트로 구현 C++ 이었으면 vector
			family[node1].child.add(node2);  
			family[node2].parent=node1;  //2의 부모는 1이라는 
		}
		
		solve(person,person2); // 7,3 목적지 
		System.out.println(answer);	
		

	}

}