주어진 password 후보들을 짧은 것부터 순서대로 입력할 때, real password가 입력되는 시간을 best case/worst case 두가지 각각 구하는 문제. 1개의 password 입력에는 1초가 소요되고 k번의 잘못된 입력마다 5초간 block이 된다.
문제 조건에서 입력 pw 들의 길이가 100자 이내이므로, 각각 pw의 길이를 구해서 길이별로 카운트한다.
일단 best/worst 모두 공통적으로 real pw 길이보다 짧은 pw들은 real pw보다 먼저 입력이 되므로, 이 짧은 pw들의 총 개수를 total로 누적한다.
best case는 real pw 길이와 같은 것들 중에서 real pw가 가장 먼저 입력되는 경우이다.
time = total + (total/k)*5 + 1
worst case는 real pw 길이와 같은 것들 중에서 real pw가 가장 나중에(더 긴 pw가 입력되기 직전) 입력되는 경우이다.
total += (real pw 길이와 같은 것들 개수, real pw 제외)
time = total + (total/k)*5 + 1
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ProblemB {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
int n = Integer.parseInt(tmp[0]);
int k = Integer.parseInt(tmp[1]);
int[] cnt = new int[101];
for (int i=0; i<n; i++) {
String attempt = br.readLine();
cnt[attempt.length()]++;
}
String realPw = br.readLine();
int realPwLen = realPw.length();
int tot = 0;
for (int i=1; i<realPwLen; i++) {
tot += cnt[i];
}
int blockCnt = tot/k;
System.out.print(tot+blockCnt*5+1);
System.out.print(" ");
tot += cnt[realPwLen]-1;
blockCnt = tot/k;
System.out.println(tot+blockCnt*5+1);
}
}
가중치가 있는 DAG(directed acyclic graph)에서 node 1→n까지 가장 많은 node를 거쳐서 가는 경로를 구하는 문제.
node, edge 갯수가 5000개 이하라서 그냥 dfs로 전체탐색했다가 TLE... (ㅠㅠ) 괜히 '자바문제일거야'하고 연장탓 하다가 C++로 고쳐서 냈는데도 TLE라서 내가 못난놈이구나 좌절하고... 자바로 풀어서 통과한 사람들도 있길래 일시적 멘붕ㅋㅋ 조금씩 고쳐서 다시 내봤지만 마지막까지 pass 못하고, 화나서(?) D번으로 넘어갔다.
끝나고 다른 사람들 풀이봤는데 dp를 썼더라. edge 갯수는 비교적 적지만 path를 따지자면 꽤 경우의 수가 많아지는 듯해서 dp로 상태를 저장해야 하는 듯 하다. 그래서 뒷북으로 dp 써서 다시 풀어봄!
dp[i][j] = (1→i 까지 오는데 길이 j인 path를 이루는 경우 걸리는 최단시간)
dpprev[i][j] = (위의 dp[i][j]의 시간이 걸리는 경우 i의 직전 node)
시간 제한인 T를 초과하지 않는 것에만 조건을 유의하면 구현은 까다롭지 않다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class ProblemC {
static int n;
static int T;
static ArrayList<Edge>[] edge;
static int[][] dp;
static int[][] dpprev;
static class Edge {
int to;
int time;
Edge(int to, int time) {
this.to = to;
this.time = time;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
n = Integer.parseInt(tmp[0]);
int m = Integer.parseInt(tmp[1]);
T = Integer.parseInt(tmp[2]);
edge = new ArrayList[n+1];
for (int i=1; i<=n; i++) {
edge[i] = new ArrayList<Edge>();
}
for (int i=0; i<m; i++) {
tmp = br.readLine().split(" ");
int u = Integer.parseInt(tmp[0]);
int v = Integer.parseInt(tmp[1]);
int t = Integer.parseInt(tmp[2]);
edge[u].add(new Edge(v, t));
}
dp = new int[n+1][n+1];
dpprev = new int[n+1][n+1];
dfs(1, 0, 1, 0);
for (int i=n; i>0; i--) {
if (dp[n][i] != 0) {
int[] path = new int[i];
int cur = n;
while (i > 0) {
path[i-1] = cur;
cur = dpprev[cur][i--];
}
System.out.println(path.length);
for (int j=0; j<path.length; j++) {
System.out.printf("%d ", path[j]);
}
break;
}
}
}
public static void dfs(int cur, int prev, int len, int sum) {
if (dp[cur][len] == 0 || sum < dp[cur][len]) {
dp[cur][len] = sum;
dpprev[cur][len] = prev;
} else {
return;
}
if (cur == n) {
return;
} else {
for (int i=0; i<edge[cur].size(); i++) {
Edge next = edge[cur].get(i);
int nextSum = sum + next.time;
if (nextSum <= T) {
dfs(next.to, cur, len+1, nextSum);
}
}
}
}
}
주어진 수열 $\{a_i\}$에서 임의의 한 element에 $+x$ 또는 $-x$ 연산을 하는 것을 k번 수행했을 때 수열의 곱 $\displaystyle\prod_{i=1}^{n} a_i$이 최소가 되게 하는 문제. 가능한 결과 수열을 아무거나 출력하면 된다.
C번의 멘붕을 간직한 채로 D번을 풀었는데 뭔가 풀 수 있을 것 같아서 희망을...!! 가졌으나 막판에 5분정도 시간이 모자라서 제출을 못했다. 근데 나중에 제출해보니 50번째 TC에서 틀려서 어차피 틀렸을 듯...
50번째 TC는 big data기도 하고 사실 왜틀렸는지 데이터로 분석은 힘들어서 소스를 다시 엄청 뜯어봤는데, 결국 원인을 찾아서 제출했더니 pass 했다. 39 line의 등호가 빠져있었던 것(ㅠㅠ)
아무튼 풀이를 정리해보자.
문제에는 k번 이하의 연산을 해서 최소가 되게 하라고 했는데, 조금만 생각해보면 연산을 하면 0이 남아있을 때를 제외하고는 무조건 이전 상태보다 곱을 더 작은 숫자로 만들 수 있어서 greedy하게 진행해도 된다. 그리고 가능한한 곱을 양수→0→음수 방향으로 진행하는게 포인트!
먼저 (0인 것들을 제외하고)현재 수열의 곱이 +인지 -인지 판단하는 변수(isPositive)를 놓고 처음 입력받을 때 음수가 들어올 때마다 flip한다.
그리고 나서는 무조건 수열에서 가장 절대값이 작은 숫자 $a_i$ 를 찾아서(절대값으로 비교를 하는 priority queue를 사용) 그것에다가 아래와 같이 연산을 취한다. (이것을 k번 반복)
