나 요리학원 출신임

순열을 이용해 풀 수 있는 문제다! 숫자를 최대 10개 사용하기 때문에 다 넣어보고 부등호를 만족한다면 그 중 가장 큰것과 작은것을 찾아내면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include using namespace std; #define ll long long ll M = 0; ll N = 1e12; int maxn[11],minn[11]; char op[11]; int a[10]; int n; bool check(){ for(int i=0;ia[i+1])) retur..

유명한 문제다! 근데 오랜만에 dp보다가 틀렸따! 먼저 dp식을 생각해보자 d[n] = n을 마지막으로 하는 가장 긴 수열로 생각하면 된다! 처음에 d[n]은 n까지 보면 가장 긴 길이라고 생각하다가 틀렸었다 n은 1000이기 때문에 그냥 for문을 돌면서 나를 기준으로 앞으로 가면서 나보다 작은수를 만날때마다 내 앞에 올수있는 것 중에서 나보다 길이가 긴 애를 가져가면 된다! 그럼 수열은 어떻게 구하면 될까? stack을 타고간다는 생각으로 나는 내 앞에 오는 작은 수만 생각하면 된다 그럼 가장 긴 수열이 만들어졌을 때 계속 내 바로 앞 숫자만 호출하면 수열이 완성된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

123더하기에서 조건이 추가되었다 바로 연속된 숫자는 사용할 수 없다는 것이다 그럼 어떻게 문제를 해결해야할까 우리는 테이블에 하나의 정보를 더 저장하면 된다! 바로 마지막 숫자다 숫자 n을 만들 때 마지막이 1이라면 n-1을 만드는 경우의 수에서 마지막이 2,3인 경우만 더하면 된다 이런식으로 나머지도 채워나가면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; #define ll long long const ll mod = 1e9+9; i..

처음 dp를 배우면 풀게되는 문제다 많이 틀리는 이유는 mod때문이 아닐까 싶다..! 수가 커질수있으니 매번 더하고 mod를 해줬다! 1,2,3으로 표현해야하므로 현재수 d[n]을 표현하는 방법은 1. d[n-1] 에 1더하기 2. d[n-2] 에 2더하기 3. d[n-3] 에 3더하기 이렇게 3가지 방법이 있다 결국 d[n] = d[n-1]+d[n-2]+d[n-3] 이다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include using namespace std; #define ll long long ll n; ll d[1000002]; const ll mod = 1e9+9; int mai..

간단한 완전탐색 문제다 경우의수가 적기 때문에 연산자가 있는대로 다 넣어보면 된다 op배열에 연산자를 넣고 해당연산자가 남아있으면 수를 줄이고 넣어서 다음 숫자로 넘어가고 다시 수를 처음처럼 늘려준다 재귀를 타고 들어가기 때문에 연산한 결과를 계속 가져갔다가 원래대로 돌려준다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #include using namespace std; int n; int op[4]; //+,-,x,/; int a[22],b[22]; int maxn = -1000000005; int minn ..

이 문제는 스택의 개념으로 풀면 된다 0이 나오면 pop 아니면 push다 물론 진짜 스택을 만들 필요는 없다 배열을 이용해서 스택처럼 쓸 수 있다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 package SWEA; import java.util.Scanner; public class Solution_d3_8931_제로 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int test_case=1;test..

Java 마스터를 위해 SWEA d3문제를 다 풀어보도록하겠다..! 이 문제는 N이 1000이하고 2개만 고르기때문에 2중포문으로 쉽게 풀 수 있다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 package SWEA; import java.util.Scanner; public class Solution_d3_9229_한빈이와SpotMart { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tes..

문제를 잘 읽어보면 한가지 알고리즘이 떠오른다 LCA!!! 간만에 떠올라서 잠깐 다시 공부하고 오랜만에 만들어봤다! 먼저 이 문제는 1이 루트고 bfs로 나머지 정점들에 순서대로 계속 가기 때문에 정점 2개씩 잡으며 lca를 구해서 lca까지의 거리를 더해가면 답을 구할 수 있다 lca만 알면 쉽게 풀 수 있는 문제다! 근데 더 어려운건 swea에서 스택메모리가 1메가라그런지 dfs로 깊이를 매기니 런타임 에러가 났다;; 대체 어디가 틀린지 몰랐는데 이게 틀렸었다;; bfs로 바꿔서 깊이를 찾았다!! 함수였던건 다 메인으로 넣어버렸다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

트라이 기본 문제다. 트라이 짜는법을 마지막으로 정적으로 배웠기 때문에 정적트라이를 이용했다! 문제를 푸는 방법은 간단하다 트라이를 만들고 cnt배열을 만들어서 지나가는 정점마다 cnt를 올려주면 된다 그럼 내가 어떤 지점에서 시작한다고 할 때 그 수만큼 cnt가 올라갈 것 이다 근데 문제는 초기화가..! 문제였다 정적으로 잡기 때문에 노드의 수를 미리 max로 두고 시작한다 여기서는 100000개의 쿼리 X 10자리수 X 알파벳 26개 다 근데 바보같이 초기화 하는 부분에서 max 크기만큼 모든배열을 계속 초기화했다 시간초과가 정확히 30번 났다 혹시 오타가 났나 계속 다시 짰는데 문제는 초기화였다 생각해보면 초기화는 내가 사용한 정점까지만 해주면 된다 trie_cnt에 저장해놨기 때문에 딱 이만큼만 ..

DP 문제다! 아직도 DP에서 실수가 많다... 완탐으로는 불가능하니까 중복되는 정보를 줄여보자 테이블은 d[현재위치][남은 점프 수]로 잡는다 처음에 틀렸던 이유는 이전에 뛰어온 곳을 저장하려고 했기 때문이였다 현재위치만 가지고 다음에 뛰어갈 곳을 구해서 정보를 업데이트하면 되는데 테이블은 이전에 정보를 가지지도 않으면서 나는 이전에 어디서 왔는지 정보를 들고다녔다 처음 테케만 나오고 바로 틀렸따~! 틀린 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include #include using namespace std; cons..