dfs로 백트래킹하면서 구해주는 완탐 문제였다 몇 번째 열을 골라서 A 혹은 B로 칠해줄 건지 구해야되는데 나는 vis[행 번호]에 칠해줄 알파벳을 써줬다. 고른 행이 1개 이상이면 k개 이상이 연속인지 확인하는 함수에서 해당 열만 바꿔준 숫자로 비교해줘서 통과하면 가장 작은 cnt개수로 갱신해줬다. import java.util.Scanner; public class Solution { static int t,d,w,k; static int[][] map; static int[] vis;// 뿌릴 약품 종류를 지정한다. a(1), b(2) static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in..
nCr = n! / r!(n-r)! 이다. 페르마의 정리는 A ^ (P-1) = 1이다. A ^ (P-2) = 1/A = A ^(-1) A = ( r!(n-r)! ) P= 문제에서 주어진수 = 1234567891 외우지 않으면 모르겠다.. package algo0419; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class S_5607_조합_Solution { static int t,n,r; static final long MOD=1234567891; static long[] fact; public static..
상하 와 좌우를 번갈아 이동해야된다. visited 배열을 3차원으로 사용했다. 마지막은 인덱스는 가로, 세로 중 어디로 이동했냐를 가르킨다. 테스트케이스 45개만 통과되는 경우 시작점 = 도착점으로 주어져서 답이 0인 것을 처리해주지 않아서 그렇다. 예외로 0을 출력하도록 구현하면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int x,y,dir; public Pos(int x,int y,int dir) { super(); this.x = x; this.y = y; this.dir=dir; } } public class Solution { static int t; static in..
푸는 데 소요시간: 40분 파이프 방향이 위일때는 다음 칸의 파이프가 방향 아래를 포함하고 있으면 된다. 이처럼 다음 칸의 방향이 내 방향의 반대인 숫자를 가지고 있나 체크해주면 된다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x,type; public Pos(int y, int x,int type) { super(); this.y = y; this.x = x; this.type=type; } } public class Solution { static int t,m,n,l; static int[][] map; static int[]..
bfs 심화랄까 벽돌을 n번 깨뜨릴 수 있는데 열의 길이 w 중에 어디를 n번 때릴지 미리 결정한 후 (중복조합) 그 다음에 bfs 돌린다고 생각해놓고 짜면 훨씬 낫다. 백준 토마토 문제처럼 연속적으로 깨지게 되는 벽돌을 모두 처리한 후 다음 bfs를 돌린다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y; int x; int num; public Pos(int y, int x, int num) { super(); this.y = y; this.x = x; this.num = num; } } public class Solution ..
set을 이용해서 문자열이 중복으로 들어가지 않도록 한 후 최종 set의 길이를 출력해주었다. import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; class Item{ int y,x; String result; public Item(int y, int x, String result) { super(); this.y = y; this.x = x; this.result = result; } } public class Solution { static int t; static int[][] map; static int[] xpos= {0,..
백준의 양팔 저울과 문제가 같은 문제인거 같다. 부분합으로 구할 수 있지만 시간초과가 나서 시간을 줄이기 위해서 이전까지 나온 결과값에 현재 점수를 더해주면서 set과 arr 리스트를 갱신해줬다. arr배열을 만든 이유는 현재 점수를 틀렸다고 가정했을 때 이전 점수와 같은 점수가 될 텐데 또 더해주지 않으면서 다음 문제 차례에 계산할 때 쓸 이전 점수들의 모음이 필요하기 때문이다. import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Solution { static int n,t; static int[] score; static Set s; static ..
1. java import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Solution { static int t,n; static int[][] map; static int[] xpos= {1,-1,0,0}; static int[] ypos= {0,0,1,-1}; static int[][] vis; public static void main(String[] args) { Scanner sc=new Scan..
사용자를 2명으로 제한해줘서 그나마 다행인 문제 충전소까지 거리가 닿냐에 따라서 사용할 수 있거나 없거나 하는데 사용하는 충전소를 중복 조합으로 만들어준다. 중복조합이라고 해서 재귀를 돌릴 필요는 없고 충전소 개수만큼 for문을 돌려주면 된다 다른 충전소이면 총 충전량을 더해주고 같은 충전소이면 충전소가 제공하는 양만큼 (충전한 곳이 하나라도 있을 경우 둘 다 거리가 안닿으면 0) 더해준다. import java.util.ArrayList; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } class Charge{ int y,x,c,p; public Charg..
나는 연결이 안된 사람을 -1로 써줬다. 플로이드 와샬 알고리즘을 볼 때 s(시작점) 중간노드 (k) e(끝 점) 의 거리를 업데이트 해줄 때 중간에 연결이 안된 사람이거나 (dist[s][k]==-1 || dist[k][e]==-1) 두 지점은 연결되어 있고 dist[s][e]가 연결이 안되어있는 상태인 경우 dist[s][e]==-1 dist[s][e]=dist[s][k]+dist[k][e]로 업데이트를 해줬다. import java.util.Scanner; public class Solution { static int t,n; static int[][] dist; public static void main(String[] args) { Scanner sc=new Scanner(System.in); ..