노는 게 제일 좋아

indexed tree로 풀었다. 하지만 어떤 이유로 indexed tree로 풀었느냐..? Indexed tree는 해당 숫자가 많은데 update가 자주될 때.. 사용하는 것 같다. 난 그랬다. https://www.acmicpc.net/problem/2243 #맞은 풀이 #include using namespace std; int idx_tree[1 단말 노드에 100만개를 넣어야하기 때문. int n; int base;// 단말 노드의 처음 idx값 //p번째 맛의 캔디의 개수를 v만큼 바꾸는 것. void update(int p, long long v) { p += (base - 1); //base - 1을 하는 이유는 B가 1부터 시작하기 때문(0번째 idx를 제외하고 숫자시작) idx_tre..

어렵지 않았다. 그냥 시키는대로만 했다. 다만... tuple을 사용할 때는.. 직접 접근이 아니면 값복사라는 사실을 간과하고 짰다.. 30분 날렸다. ㅎ https://www.acmicpc.net/problem/1713 #맞은 풀이 #include #include #include #include using namespace std; vector frame; int N; int student; bool cmp(tuple& t1, tuple& t2) { if (get(t1) == get(t2)) { if (get(t1) == get(t2)) return get(t1) > get(t2); else return get(t1) < get(t2); } return get(t1) < get(t2); } int ma..

어려웠다. 우선순위 큐를 이렇게 이용한다는 것이 나에겐 조금 어려웠다. 시간을 보아하니 절대로 Brute Force, 전수조사는 아니었다. 힌트를 보고나서야 풀 수 있었다. https://www.acmicpc.net/problem/1655 #맞는 풀이 #include #include using namespace std; int N; priority_queue minH; priority_queue maxH; int main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> N; for(int i = 1; i> x; //min에 넣을지 max에 넣을지?? //한쪽에만 몰아넣으면 안된다. //그렇게 하면 중간값을 바로 알 수 없어서 둘의 사이즈를 항상 차이가 1만큼만 나게 해..

시간초과가 왜 난지 몰랐지만.. 그냥 나중에 생각해보니 날만했었다. https://www.acmicpc.net/problem/1062 #맞은 풀이 #include #include #include #include using namespace std; bool alpha[26]; int N, K; vector vec; int ans = 0; //idx를 추가시켜서 시간을 단축 시켰다. //여기서 idx는 for문이 시작하는 번호를 말한다. void func(int cnt, int idx) { //K-5개만큼 골랐다면 if (cnt == K-5) { int cnt = 0; //각 단어를 읽을 수 있는지 조사 for (string str : vec){ bool read = true; //만약 모르는 글자가 나오..

사실 어렵다기보다는 생각이 어렵다. 구현은 어렵지 않다. 솔직히 힌트를 얻어서 했지만.. 과연 내가 혼자서 할 수 있을까?? 는 고민이다. https://www.acmicpc.net/problem/2842 #맞은 풀이 #include #include #include //distance를 쓰기 위함 #include using namespace std; const int MAX = 51; const int INF = 987654321; char pos[MAX][MAX]; int height[MAX][MAX]; int visited[MAX][MAX]; int dr[8] = { -1,-1,-1,0,0,1,1,1 }; int dc[8] = { -1,0,1,-1,1,-1,0,1 }; set h; int N; int..

DP는 항상 봐도 이해하고 나야 쉽지..그 전엔 어렵다 https://www.acmicpc.net/problem/1103 #맞은 풀이 #include #include #include using namespace std; const int MAX = 51; int r, c; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int ans = 0; //최대 동전 움직인 횟수. bool chkInf = false; int map[MAX][MAX]; int visited[MAX][MAX]; //int finished[MAX][MAX]; int dp[MAX][MAX]; //cr,cc는 위치를 위함 cnt는 동전 움직인 횟수를 위함. void DFS(int cr, int ..

물론 이것도 DP 문제다. 왜냐하면.. 경우의 수가 무지막지하게 늘어나기 때문이다. 이런 실버 1문제를 1시간이나 걸리다니... 예외를 찾는게 너무 오래걸렸다. https://www.acmicpc.net/problem/2011 #맞은 풀이 #include #include #include using namespace std; const int DIV = 1000000; string s; long long dp[5001]; int num[5001]; int main() { cin >> s; int length = s.size(); long long ans; //1부터 시작하게 바꿈. for (int i = 0; i < length; i++) { num[i + 1] = s[i] - '0'; //문자열이므로 i..

이전의 1학년 문제와 같다. 다만 경우의 수를 고려하는 것이 아닌 그냥 최댓값이 무엇이냐?라는 것이다. 그래서 솔직히 BFS로 풀어볼까도 생각했었다. 결국 N번째 도착지만 알면 되니까..? 아무튼 근데 그냥 DP로 풀었다. 점화식이 조금 더 직관적이어서 그랬다. https://www.acmicpc.net/problem/1495 #맞은 풀이 #include #include using namespace std; int N, S, M; int arr[52]; int dp[52][1001]; //dp[i][j]는 i번째에 볼륨 j를 가질 수 있는지 여부(-1, 1); int main() { cin >> N >> S >> M; //N개의 곡 입력받음.(첫번째 곡은 주어졌고 N번의 볼륨을 변화시켜야함 //총 N+1..

솔직히 바로 생각을 못했다. 값을 다 계산해야하나? 싶었다. 하지만 힌트를 보고야 말았으니.. 즉, N개의 수에서 N-1번만 조사하면 되는 것이고 N-1까지의 경우의 수를 구하려면..? N-2에서 N-1번째 원소를 더하거 나 빼는 경우를 세어주면 되었다. https://www.acmicpc.net/problem/5557 #맞은 풀이 #include using namespace std; int N; int arr[101]; long long dp[101][21]; //N번째에 K값이 나오는 경우의 수 int main(){ long long ans; //답의 범위가 2^63-1임 cin >> N; for(int i =1; i> arr[i]; } int target = arr[N]; //초기값 dp[1][ar..

처음에 감을 못잡았는데.. N-1번째에 사자를 놓느냐 마느냐를 집중했어야 했는데 사자가 1마리 일때, 사자가 2마리 일때, 사자가 3마리 일때의 규칙을 찾으려니까 못찾았다. 나의 실수다. 시간제한을 보니 2초다. 또한 최소 100,000개의 배치를 해야한다. 배열로 만들지 고민했다. https://www.acmicpc.net/problem/1309 #맞는 풀이 #include using namespace std; int N; const int MAX = 100001; int dp[MAX][3]; //120만 바이트 -> 1.2메가정도 int main(){ cin >> N; dp[1][0] = 1; //1번째 줄에 아무것도 놓지 않는 경우 dp[1][1] = 1; //1번째 줄에 왼쪽에 사자를 놓는 경우 ..