성공을 즐기자

문제는 아주 간단하다 N이 주어질때 N*N 체스판에서 N개의 퀸을 놓는 방법의 수를 출력하면 된다. 일단 코드는 check 와 queen 함수를 사용하였다. #include using namespace std; int col[16],cross1[30], cross2[30];//15*2-1 = 29이므로 약 30 int cnt, n ; bool check(int r, int c) { // 놓을 수 있는 자리인가 if (col[c] || cross1[r+c] || cross2[r-c+n-1]) return false; return true; } void queen(int row) { //row 행에 퀸 놓을 자리 찾기 if (row == n) {// 방법 하나 발견! cnt++; return; } for (..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제의 특별한 점 1 . 대각선으로 이어지는 것도 고려해야한다. 2 . 0을 두개 입력받으면 반복문이 종료되어야한다. 대각선으로 이어지는 것도 고려해야한다. 그림을 그려서 대각선까지 갈 수 있도록 dx, dy를 만든다. [배열의 크기는 8] ( i , j ) 를 중심으로 8개의 칸을 생각한다. 8개의 칸 중 하나의 칸을 선택해 돌려가면서 dx는 i의 값을 , dy 는 j의 값으로 배열을 ..

문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 간단 풀이 : 1) 토마토을 입력받으면서 - 익은 토마토(1)가 들어온다면 q에 넣고 dis를 0으로 설정한다. - 익어야하는 토마토(0)이 들어온다면 dis를 -1으로 설정한다. 2) 전형적인 bfs의 while문을 돌린다. - 범위를 벗어나거나 -1이 아니라면(익지않은 토마토에서 값이 변경된경우) continue한다. - 새로운 위치의 dis를 원래 위치의 dis+1 ..

문제 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이방법 : 2개의 벡터, 1개의 스택을 이용해 풀이하였습다. 0) n을 입력받고 v2라는 답을 저장할 벡터를 생성한다. 1) vector에 n개의 숫자를 입력받는다. 2) stack에 index를 넣는다. 3) stack에 있는 index값에 해당하는 vector값과 i값을 비교한다. 4)( i값은 stack에 있는 값보다 항상 오른쪽 값이므로) 큰 값을 v2벡터에 넣는다. 5) v2벡터를 출력한..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 풀이 방법 : 띄어쓰기(공백문자)와 함께 문자들을 입력받는다. 그 후 한 글자(char)씩 ()[]를 구별하여 짝이 맞는지 확인하고 맞으면 yes, 아니면 no을 출력한다. 정답코드 : #include #include // getline을 위해 #include using namespace std; bool isok; int main() { while (1) { isok = true;..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 정답 코드: 더보기 #include #include #include using namespace std; int v, e, start; using PI = pair; #define INF 2e9; int visit[20001]; int dist[20001]; vector V; priority_queue q; int main() { cin >> v >> e >> start..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 LIS(최장 증가 부분 수열)으로 이와 비슷한 백준문제(같이 풀면 좋을 문제)에는 가장 긴 감소하는 부분 수열 [11722번] 가장 긴 바이토닉 바이토닉 부분 수열 [11054번] 상자넣기[1965번] 전깃줄[2565번] 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 티어 : 실버 1 => 포도주의 개수와 각각의 양이 주어질때, 3번연속으로 마시지 못한다는 제한이 있다. 이때 마실 수 있는 포도주의 양을 출력하는 문제이다. 해설 : DP를 이용하여 푸는 문제다. 3번연속으로 마실수 없다는 것을 염두해서 풀이해야한다. 크게 두가지의 경우가 있다. 1) n번 포도주를 마시지 않는 경우 2) n번 포도주를 마시는 경우 n번째를 마시는 경우에는 또 2가지의 경우로..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 백준 티어 : 실버1 => 삼각형이 입력되고 (0,0)을 시작으로 삼각형의 마지막줄까지 최대가 되는 경로를 찾아 출력하는 문제이다. 해설 : DP를 이용하여 풀이하면된다. 숫자를 저장할 이차원배열(mp) 과 최대 경로를 저장할 이차원배열(cache) 을 정의한후 재귀를 이용한 dp로 풀이한다. 정답 코드 : #include #include #include using namespace std; int n; int mp[501][501],cache[501][501]; in..

https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 백준티어 : 실버1 입력 첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다. 출력 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. 예제 입력 1 복사 4 3 예제 출력 1 복사 1+2+1 => n과 k가 입력될때 총 합이 n이 되는 1,2,3의 합으로 이루어진 식의 k번째 식을..