묶음의 개수 P가 정해졌을 때 각 묶음의 달란트를 곱한 수가 크려면 각 묶음의 달란트가 최대한 골고루 분배되어야 된다는 것을 알 수 있다. 일단 달란드 개수 N/P는 각 묶음의 최소 달란트 개수로 초기화해준다. 그러면 N%P만큼의 분배되지 않은 달란트가 남을 것인데 해당 달란트들은 골고루 +1씩 해줘서 나눠준 후 곱하면 된다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include using namespace std; int n, t, p; long long ans; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; for (int tc = 1; tc > n >..
n개의 자성체들 사이에는 n-1개의 균형점이 무조건 존재한다고 보고 양 자성체들을 각각 s,e로 놓고 균형점(mid)의 위치를 이분탐색으로 찾아나간다. 오차범위가 무슨 말인지 못하다가 대략 이해했는데 만약 이분탐색으로 양쪽의 힘이 딱 같은 곳을 못발견한채로 s>e가 되어버리는 순간이 있다면 균형점 mid를 찾아야되는데 범위를 넘어가버린다는 것은 이분탐색으로 정확히는 모르지만 s와 e사이에 균형점이 있기는 있다는 것이다. 그럼 세부 좌표 오차일 것이므로 해당 mid를 출력해버리면 된다. s에 1e^12를 빼거나 e에서 뺐을 때 범위를 넘어가면 두 좌표 사이의 거리는 그것보다 작은 것이니까 그 사이에 무조건 있다. 그래도 mid를 출력해도 되는 이유는 10자리까지만 출력하기 때문인 것 같다. #include..
입력받은 문자열의 실제 숫자 개수를 배열에 저장한다 (인덱스 = 숫자) 숫자 개수만큼 다시 문자열 형태로 출력해준다. #include #include using namespace std; int t; int getNum(string str) { if (str == "ZRO")return 0; if (str == "ONE")return 1; if (str == "TWO")return 2; if (str == "THR")return 3; if (str == "FOR")return 4; if (str == "FIV")return 5; if (str == "SIX")return 6; if (str == "SVN")return 7; if (str == "EGT")return 8; else return 9; } s..
일단 1~18 사이 소수를 먼저 구해준 후 A가 소수 개를 성공할 확률, B가 소수 개를 성공할 확률을 구한다. 만약 A가 2개를 성공한다고 칠 때 18개의 구간 중 어느 구간 2개에서 성공하는 지를 구해줘야 하므로 18C2를 구해서 a의 2개 성공확률에 곱해줘야 된다. 둘 중 적어도 하나가 소수인 확률은 전체확률인 1에서 둘다 소수가 아닌 확률(여집합)을 빼주면 된다. 교집합을 구하는 방법과 소수개를 성공할 확률을 구하는 것까지는 잘 했는데 조합을 구해줘야 된다는 것을 떠올리지 못해 못 풀어서 해당 부분은 참고해서 했다. 조합은 nCr=n-1Cr-1 +n-1Cr의 식을 참고하여 이중배열로 미리 구해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #inc..
최대 6자리 숫자의 자리수 중에 2개를 고르는 것: 6C2 =15가지 최대 10번 자리 교환한다 15의 10승=> 시간초과 따라서 VISIT방문 처리를 해주거나 다른 방법으로 풀어야되는데 다른 사람걸 보고 VISIT[만든숫자][교환횟수]=TRUE 이런식으로 해주면 된다. 백준의 토마토 3차원문제가 이런식으로 했던거 같은데 가끔 잊을만하면 나온다 #include #include #include #include using namespace std; int result; bool visit[1000000][11]; int toNumber(string s){ int temp=0; for(int i=0;iresult)result=temp; return; } for(int i=0;it; for(int tc=1;tc..
높이를 깎아서 다른 높이를 전달할 수 있다 => 같은 위치더라도 다른 높이로 들어온다. 방문정보를 어떻게 전달할 지 몰라서 방문 처리가 어려워 dfs로 했다 package algo0424; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; int cut; intnum; int len; public Pos(int y, int x,int cut,int num,int len) { super(); this.y = y; this.x = x; this.cut=cut; this.num=num; this.len=len; } } public class S_1949_등산로조성_Solution { ..
1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음) 2. 0인 곳의 처리 (bfs) 0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다. 0의 개수만큼 cnt를 1증가시켜준다. 3. 1이상 숫자인 곳의 처리 마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Sc..
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..
풀이 참고 mygumi.tistory.com/180 package algo0421; import java.util.Scanner; public class S_5604_구간합_Solution { static long t,a,b; static long[] count; static long point; public static void main(String[] args) { Scanner sc=new Scanner(System.in); count=new long[10]; point=1;//초기화 a=1; b=sc.nextLong(); while(a