a라는 사람과 b사람이 벌꿀을 채취하는데 벌집이 중복되지 않도록 해야된다. a라는 사람은 모든 행, 열 기준으로 고르는데 b라는 사람은 a와 같은 행이라면 열이 중복되지 않도록 해야하고 다른 행이면 상관없이 뽑는다. 1. collect 함수 a는 모든 경우를 전사적으로 구해주므로 list에 집어넣는다. (추후 다른 행이면서 열이 중복된 경우를 계산할 때 쓴다) b는 a와 행이 겹치지 않는 부분에서 subset을 돌려준다. 일단 이 함수에서 a의 최대값과 b의 최대값의 합의 최대값으로 answer를 갱신해주면 행은 같은 경우는 끝난다. 2. calculate함수 다른 행의 중복된 열을 구해준다. a라는 사람은 collect함수에서 전사적으로 모든 subset 경우를 구해줬다. a사람이 구한 리스트지만 이제..
처음에 플로이드 와샬로 풀었는데 t의 자리에 tc를 넣었다가 런타임에러 났었다. 내일 다시 플로이드 와샬로 풀어봐야지 내 위치에서 dfs로 돌면서 next(나보다 큰 친구들)의 count값을 증가시키면 next입장에서는 작은 애들의 개수만큼 업데이트가 된다. temp는 dfs를 도는 횟수를 가르키는데 현재 내 번호보다 큰 친구들의 수(나 포함)로 count[내번호]+temp 해주면 나보다 큰 친구들의 수를 구할 수 있다. 이렇게 temp로 업데이트 (나 포함해서 나보다 큰 친구들의 수) + count[next] 업데이트 (나보다 작은 친구수만큼 증가) 의 합이 n이 되면 나의 순서를 알 수 있는 경우이다. import java.util.ArrayList; import java.util.Scanner; p..
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..
www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다. 칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하..
푸는 데 소요시간: 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 ..