- Today
- Total
- dp
- Algorithm
- ๋ฌธ๋ฒ
- pytorch
- MST
- ๋ฐฑ์ค
- spring
- PS
- CS
- ๋ค์ต์คํธ๋ผ
- OOP
- ์์์ ๋ ฌ
- Graph
- ํ๋ก๊ทธ๋๋จธ์ค
- ์กธ์ ์ํ
- leetcode
- ์๋ฐ์์ ์
- array
- ๋ฐฑ์๋
- BFS
- ๊ตฌํ
- ์ธํด
- database
- ์๋ฐ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ๋ฒจ๋งํฌ๋
- java
- ์๋ฃ๊ตฌ์กฐ
- tree
- ๊ทธ๋ฆฌ๋
Partially Committed
[๋ฐฑ์ค 2798/2231/14889/2606] ์๋ฐ ๋ณธ๋ฌธ
A. ๋ธ๋์ญ BOJ 2798
https://www.acmicpc.net/problem/2798
2798๋ฒ: ๋ธ๋์ญ
์ฒซ์งธ ์ค์ ์นด๋์ ๊ฐ์ N(3 ≤ N ≤ 100)๊ณผ M(10 ≤ M ≤ 300,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์นด๋์ ์ฐ์ฌ ์๋ ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ์ด ๊ฐ์ 100,000์ ๋์ง ์๋ ์์ ์ ์์ด๋ค. ํฉ์ด M์ ๋์ง ์๋ ์นด๋ 3์ฅ
www.acmicpc.net
๋์ด๋ | Bronze 2 |
ํ์ด ์๊ฐ | 10 ๋ถ |
๋ถ๋ฅ | ๋ธ๋ฃจํธํฌ์ค |
์๊ฐ๋ณต์ก๋ | |
๊ณต๊ฐ๋ณต์ก๋ | O(100+100) |
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int ans = -1;
static int m;
static int n;
static int [] arr;
static int [] nums = new int[3];
static boolean [] visited;
private static void dfs(int k){
if(k==3){
int sum = 0;
for(int i = 0 ; i < 3; i++){
sum += nums[i];
}
if(sum > m) {
return;
} else { // sum <=m
ans = Math.max(ans, sum);
return;
}
} else {
for(int i = 0 ; i < n ; i ++){
if(!visited[i]){
visited[i] = true;
nums[k] = arr[i];
dfs(k+1);
visited[i] = false;
}
}
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk;
stk = new StringTokenizer(br.readLine());
n = Integer.parseInt(stk.nextToken());
m = Integer.parseInt(stk.nextToken());
arr = new int[n];
visited = new boolean[n];
stk = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i ++){
arr[i] = Integer.parseInt(stk.nextToken());
}
dfs(0);
bw.write(ans+"\n");
bw.flush();
bw.close();
}
}
B. ๋ถํดํฉ BOJ 2231
https://www.acmicpc.net/problem/2231
2231๋ฒ: ๋ถํดํฉ
์ด๋ค ์์ฐ์ N์ด ์์ ๋, ๊ทธ ์์ฐ์ N์ ๋ถํดํฉ์ N๊ณผ N์ ์ด๋ฃจ๋ ๊ฐ ์๋ฆฌ์์ ํฉ์ ์๋ฏธํ๋ค. ์ด๋ค ์์ฐ์ M์ ๋ถํดํฉ์ด N์ธ ๊ฒฝ์ฐ, M์ N์ ์์ฑ์๋ผ ํ๋ค. ์๋ฅผ ๋ค์ด, 245์ ๋ถํดํฉ์ 256(=245+2+4+5)์ด
www.acmicpc.net
๋์ด๋ | Bronze 2 |
ํ์ด ์๊ฐ | 5 ๋ถ |
๋ถ๋ฅ | ๋ธ๋ฃจํธํฌ์ค |
์๊ฐ๋ณต์ก๋ | O(N) |
๊ณต๊ฐ๋ณต์ก๋ | O(1) |
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int ans = -1;
static int m;
static int n;
static int [] arr;
static int [] nums = new int[3];
static boolean [] visited;
private static void dfs(int k){
if(k==3){
int sum = 0;
for(int i = 0 ; i < 3; i++){
sum += nums[i];
}
if(sum > m) {
return;
} else { // sum <=m
ans = Math.max(ans, sum);
return;
}
} else {
for(int i = 0 ; i < n ; i ++){
if(!visited[i]){
visited[i] = true;
nums[k] = arr[i];
dfs(k+1);
visited[i] = false;
}
}
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk;
stk = new StringTokenizer(br.readLine());
n = Integer.parseInt(stk.nextToken());
int ans = n+1;
for(int i = 1 ; i<=n-1; i++){
int target = i;
int save = target;
int pSum=target;
while(target>0){
pSum += target%10;
target = target/10;
}
if(pSum == n){
ans = Math.min(ans, save);
}
}
if(ans==n+1){
bw.write(0+"\n");
} else {
bw.write(ans+"\n");
}
bw.flush();
bw.close();
}
}
C. ์คํํธ์ ๋งํฌ BOJ 14889
https://www.acmicpc.net/problem/14889
14889๋ฒ: ์คํํธ์ ๋งํฌ
์์ 2์ ๊ฒฝ์ฐ์ (1, 3, 6), (2, 4, 5)๋ก ํ์ ๋๋๋ฉด ๋๊ณ , ์์ 3์ ๊ฒฝ์ฐ์๋ (1, 2, 4, 5), (3, 6, 7, 8)๋ก ํ์ ๋๋๋ฉด ๋๋ค.
www.acmicpc.net
๋์ด๋ | Silver 2 |
ํ์ด ์๊ฐ | 30 ๋ถ |
๋ถ๋ฅ | ๋ฐฑํธ๋ํน |
์๊ฐ๋ณต์ก๋ | O(nC_n/2 + n^2) |
๊ณต๊ฐ๋ณต์ก๋ | O(20*20+20*2) |
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int n;
static long ans = Integer.MAX_VALUE;
static int[][] power;
static int[] entry;
static boolean[] visited;
private static void getScore() {
long ret = 0;
long A = 0;
long B = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i; j < n; j++) {
if (visited[i] == true && visited[j] == true) {
A+=(power[i][j]+power[j][i]);
} else if (visited[i] == false && visited[j] == false) {
B+=(power[i][j]+power[j][i]);
}
}
}
ans = Math.min(ans, Math.abs(A-B));
}
private static void dfs(int k, int idx) {
if (k == n/2) {
// ์ ์ ๊ณ์ฐ
getScore();
return;
} else {
for (int i = idx; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(k + 1, i + 1);
visited[i] = false;
}
}
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk;
n = Integer.parseInt(br.readLine());
power = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
power[i][j] = Integer.parseInt(stk.nextToken());
}
}
dfs(0, 0);
bw.write(ans + "\n");
bw.flush();
bw.close();
}
}
D. ๋ฐ์ด๋ฌ์ค BOJ 2606
https://www.acmicpc.net/problem/2606
2606๋ฒ: ๋ฐ์ด๋ฌ์ค
์ฒซ์งธ ์ค์๋ ์ปดํจํฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ปดํจํฐ์ ์๋ 100 ์ดํ์ด๊ณ ๊ฐ ์ปดํจํฐ์๋ 1๋ฒ ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋งค๊ฒจ์ง๋ค. ๋์งธ ์ค์๋ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ ์์ ์๊ฐ ์ฃผ์ด
www.acmicpc.net
๋์ด๋ | Silver 3 |
ํ์ด ์๊ฐ | 5 ๋ถ |
๋ถ๋ฅ | ๊ทธ๋ํ ํ์ |
์๊ฐ๋ณต์ก๋ | O(V+E) |
๊ณต๊ฐ๋ณต์ก๋ | O(V+E) |
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] graph;
static boolean [] visited;
private static void dfs(int v){
if(!visited[v])
visited[v] = true;
for(int cur : graph[v]){
// ์ฐ๊ฒฐ ๋
ธ๋ ํ์
if(!visited[cur]){
visited[cur] = true;
dfs(cur);
}
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk;
int n = Integer.parseInt(br.readLine()); // ๋
ธ๋์ ์
int m = Integer.parseInt(br.readLine()); // ์ฃ์ง์ ์
graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++)
graph[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
graph[a].add(b);
graph[b].add(a);
}
visited = new boolean[n+1];
dfs(1);
int cnt = 0;
for(int i = 2 ; i<=n; i++){
if(visited[i]){
cnt++;
}
}
bw.write(cnt+"\n");
bw.flush();
bw.close();
}
}
'๐ฅ Algorithm || ๋ฌธ์ ํ์ด > PS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค 1436/10815/11054/16139/16928] ์๋ฐ (0) | 2023.02.16 |
---|---|
[๋ฐฑ์ค 7568/1904/1018/25682/2110] ์๋ฐ (1) | 2023.02.15 |
[๋ฐฑ์ค 2580/14888/13305/10844] JAVA (0) | 2023.02.13 |
[๋ฐฑ์ค 1463] 1๋ก ๋ง๋ค๊ธฐ (JAVA) (0) | 2023.01.27 |
[๋ฐฑ์ค 1947] ์ ๋ฌผ ์ ๋ฌ (JAVA) (0) | 2023.01.27 |