공부혜옹

재귀를 이용해 모든 수의 조합을 구하면 되는 문제였다. 단, 수열의 길이제한이 있으므로 해당 조건은 탈출조건으로 설정한다 #include #include #include #include using namespace std; int n, m; int arr[9]; int ans[9]; void func(int index, int cnt){ if(cnt == m) { for(int i=0; i m; for(int i=0; i> arr[i]; } sort(arr,arr+n); func(0,0); return 0; }

쉬운 문제였는데 테스트케이스를 몇개 줄건지 말을 안해줘서 while(cin >> n) 부분을 빼먹었더니 틀렸던 문제다..화가 난다 풀이 방법은 각자의 숙련도가 들어올때마다 비트마스킹해서 그 값과 기존의 숙련도 비트 리스트와 비교해 리스트에 동일한 값이 있으면 넘어가고 없으면 리스트에 추가했다. 마지막으로 정답은 해당 리스트의 크기를 출력해주었다 푼사람이 없어서 적절한 풀이인지는 잘 모르겠지만 일단 정답처리는 되었다. 아마 비슷한 맥락내에서 더 효율적으로 구현하는 방법이 있을듯! #include #include #include using namespace std; int n; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); while(cin>>n){ ..

비트마스크 문제중에 쉬운편이었다. 풀이방법은 1. 단어를 비트마스킹해서 비트로 표현한다 2. 비트로 이루어진 온전한 알파벳판을 만든다 ex) a, b 만 있는 판은 -> 00000011 이런식으로 3. 1번케이스와 2번 케이스를 나누어 구현한다 3-1. 1번케이스의 경우 XOR 연산( 둘중 하나만 1일경우 1 )을 이용해 해당 알파벳 비트를 0으로 만든다 3-2. 2번케이스의 경우 OR연산( 둘중 하나라도 1일경우 1 )을 사용해 해당 알파벳 비트를 1로 만든다 4. 이렇게 만들어진 알파벳판과 본래의 단어비트를 &연산 ( 둘 다 1이여야 1 )한 값이 본래의 단어비트와 같은지 확인한다 5. 같을경우 cnt를 증가시켜서 갯수를 세어준다 로 단어를 비트로 바꾸고 비트연산을 할 줄 알면 풀 수 있는 문제였다...

처음엔 정사각형이 되지 않을 조건을 먼저 생각해 보았는데 정사각형 특성상 정사각형일때만 해당되는 조건이 훨씬 명확하고 적은것같아 방향을 바꾸었다. 정사각형이 될 조건은 1. 모든 변의 길이가 같다 2. 대각선의 길이가 서로 같다 주어지는 네개의 점을 이용해 거리를 계산하면 6개의 길이가 나온다 이때 점을 미리 사각형의 형태로 나열한 후 거리를 구하는것 보다 일단 6개의 길이를 다 구한후 sort하면 나머지 두개의 길이가 대각선의 길이임을 알 수 있다. (정사각형은 변의 길이보다 대각선의 길이가 항상 길기 때문) #include #include #include #include using namespace std; int t; int x1, x2, yy1, y2; int func(int x1, int yy1..

어떻게 하면 효율적으로 풀 수 있을까 치킨집 주위로 가까운집이 몇갠지 세서 통계내야하나 별 생각을 다하다가 결국 dfs를 이용해 완전탐색하기로 했다. 치킨집 조합을 모두 구해서 각 조합별 도시의 최소치킨거리를 구해 가장 작은 치킨거리를 보유한 조합을 선택한다. #include #include #include #include using namespace std; int n,m ; int arr[51][51]; bool check[14]; int ans = 987654321; vector chicken; vector home; int calc(pair a, pair b){ return abs(a.first-b.first) + abs(a.second-b.second); } void DFS(int idx, in..

보자마자 가장 큰 자릿수에 있는 알파벳부터 차례대로 숫자를 부여해 계산하면 되겠다라고 간단히 생각해서 코딩하다가 그렇다면 다른자릿수에 있는 같은 알파벳 ex) abcd + gaf 에서 a의 경우는 어떻게 처리해야할지 막막해졌다.. 따로 저장해서 일일히 표기를 해둘까하다가 내가 생각한 접근방법이 처음 부터 틀렸다는 생각이 들었고 다시 로직을 짜기 시작했다. 우선 가장 큰자릿수에 가장큰 수 9를 적용해야 수의 합이 최대가 된다는것은 명확한 사실이다. 문제는 가장 큰자릿수의 알파벳이 무엇인지 판별하는것. 처음에 보이는 자릿수에 따라서 무턱대고 숫자를 부여했다면 이번엔 글자 자체에 자릿수를 한번 부여해보는식으로 접근했다. 위 이미지에서 c의 경우 1000자리와 10자리 두군데에 분포해있기 때문에 c라는 알파벳 ..

배열의 원소값이 1인 부분만 사각형의 일부가 될 수 있기 때문에 0인 부분을 제외하고 생각한다. 1을 만났을때 이것이 정사각형일지 아닐지를 판단하는것이 문제 1을 만날 경우 1의 왼쪽, 왼쪽 대각선위, 위쪽 총 세부분을 검사해 가장 작은 수를 찾아 +1해주면 그것이 해당 사각형 한변의 최대 길이가 된다. 이것을 식으로 표현하면 다음과 같다 arr[i][j] = min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1]) +1 예상치 못하게 fail을 받은 문제인데 '다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.' 이 주어지는 숫자 배열이 실제 숫자가 아니고 string으로 주어지기 때문에 int가 아닌 string으로 받아 인덱스 - 48을 해주어야한다. #include #inc..

도형에다가 dp 문제이기 때문에 도형을 일단 하나하나 그려보면서 규칙성을 찾고자 했다. 3X4사이즈의 벽을 그리던 와중 3X2벽에서 나온 타일의 패턴을 이용할 수 있겠다는 생각이 들어서 바로 3 * 3 = 9 가지구나! 라고 생각하고 코드를 구현했는데 당연히 틀렸다. 왜냐하면 3X2의 패턴말고 추가 패턴이 2가지 더 나오기 때문이다 (빨간 동그라미 친 패턴) 풀겠다는 의지를 가지고 3X8까지 그려본 결과 각 단계별로 추가 패턴은 2개가 나온다는 것을 확인했다. 3X6의 패턴을 파악하던중 중복이 나올 수 있다는것을 알게되었고 중복을 피하고자 하는 방법을 찾기 시작했다. 패턴을 케이스 별로 나누어 생각하는것인데 첫번째 케이스의 경우 이전과 같은 논리로 3X2의 패턴경우의 수 * 3X4의 패턴경우의 수 를 해..