알고리즘/백준 문제풀이

백준-영화감독 숌(1436번)

문제 6이 3개이상 '연속'으로 들어간 숫자를 찾는것이 문제입니다. n을 입력받고 n번째 해당 숫자를 출력해주면 됩니다. 풀이 #include using namespace std; int main() { int n; cin >> n; int count = 0; int number = 0; //영화제목숫자 while (count != n) { number++; int temp = number; while (temp >=666) { if (temp % 1000 == 666) { count++; break; } temp = temp / 10; } } cout = 666) { if (temp % 1000 == 666) { count++; break; } temp = temp / 10; } 이 부분입니다. tem..

백준-체스판 다시 칠하기(1018번)

문제 n,m값을 입력받습니다. row: n, col: m 을 가지는 체스판이라고 가정합니다. 각 칸마다 W또는 B를 입력받습니다. 가장 좌측위가 W인 체스판, 또는 B인 체스판으로 구성하고자 하는데, 이떄의 크기는 8x8로 만들어주려고 합니다. 임의의 위치에서 잘라서 8x8체스판을 만들려고 하는데 그 중에서 정상적인 체스판으로 만들기 위해서, 다시 칠해야 하는 최소의 칸 수를 구하는 문제 입니다. 풀이 저 같은 경우는 먼저 n,m을 입력받은 후, 동적할당을 통해 2차원 배열을 만들어 주었습니다. (참고로 int** arr 은 전역변수로 만들었습니다. 함수 속에서 사용하기 위해서+ 함수 매개변수를 줄이려고) int n,m; cin>>n>>m; arr=new int*[n]; for(int i=0; i

백준-덩치(7568번)

문제 먼저 전체 사람수 n을 입력받습니다. 그리고 n명의 (키,몸무게)를 순서대로 입력받습니다. 그 후에 각자의 덩치 순위를 빈칸으로 구분하여 출력해주는 문제입니다. (덩치는 키,몸무게가 상대보다 둘 다 커야 덩치가 큰 판정입니다.) 풀이 (키,몸무게)를 쌍으로 입력받는다... 이건 std::pair를 쓰라고 만들어준 문제라고 보여집니다 (std::pair 사용법 확인하기) #include //#include --> vector나 algorithm 헤더파일에 포함되어 있습니다. #include using namespace std; //(x,y) = (몸무게, 키) int main() { int n; cin>>n; vector v; //입력 for(int i=0; i>x>>y; pair temp=make_..

백준-분해합(2231번)

브루트포스 알고리즘 문제입니다. 코드에서 jari=자릿수 // 123이면 jari=3 #include #include using namespace std; int main() { int n; cin>>n; int jari=to_string(n).length(); //자릿수 if(jari==1) { for(int i=1; i

백준-블랙잭(2798번)

n,m을 입력받습니다. 주의할점은 뽑은 3장의 카드합이 m보다 크면 안되고 최대한 m에 가까운값을 찾아야 한다는 것입니다. 브루트포스 알고리즘 문제로 가능한 모든 경우를 단순히 다 따져주면 되는 문제입니다. 어렵지 않기 때문에 코드만 첨부하겠습니다. #include using namespace std; int main() { int n,m; cin>>n>>m; int* arr=new int[n]; for(int i=0; i>arr[i]; } int sum=-1; for(int i=0; i

백준-하노이 탑 이동 순서(11729번)

유명한 하노이탑 문제입니다. 입력으로 원판의 갯수 n 을 입력받으면 최소 이동 횟수를 출력해주고 그 과정을 출력할것을 요구하고 있습니다. 하노이탑의 패턴 모든 재귀함수가 그렇듯이 패턴을 찾는것이 중요합니다. 하노이탑의 패턴은 크게보면 가장 아랫부분 원판을 제외한 나머지를 잠깐 1->2번으로 옮겨놓는다. 가장 아랫부분 원판을 1->3으로 옮긴다 2에 옮겨놓았던 원판들을 2->3으로 옮겨놓는다. 이 패턴을 인지하는 순간 재귀함수를 세우는건 쉬워집니다. 하노이탑 최소 이동 횟수 하노이탑의 최소 이동횟수는 (2의 n승)-1 입니다. 그 이유는 위에서 말한 규칙을 보면 알 수 있습니다. 가장 아랫부분 원판을 제외한 나머지를 잠깐 1->2번으로 옮겨놓는다. 가장 아랫부분 원판을 1->3으로 옮긴다 2에 옮겨놓았던 ..

백준-별 찍기 -10(2447번)

별찍기 문제중 어려운 편에 속하는 문제인것 같습니다. 이 문제는 규칙을 찾는것이 핵심이라고 생각합니다. 입력된 n값에 따른 한 가운데 빈칸 부분을 중심으로 생각하면 이해하기가 쉬울 것 같습니다. 먼저 가장 기본인 n=3일때의 모양은 다음과 같습니다. *의 위치를 좌표평면으로 생각해보겠습니다. (단, 오른쪽으로가면 x가 증가, 아래로갈수록 y가 증가한다고 생각) n=3일땐 (2,2)가 빈칸이 됩니다. 그럼 n=3일때의 모양이 가로로 반복된 아래그림은 빈칸을 어떻게 특정할 수 있을까요? 빈칸의 좌표를 생각해보면 (2,2) , (5,2) , (8,2) , (11,2) , (14,2) , (17,2) , (20,2) , (23,2) , (26,2) 인것을 알 수 있습니다. 그럼 n=3일때의 모양이 세로로 반복된..

백준-재귀함수가 뭔가요?(17478번)

딱히 설명할 것이 없는 문제인 것 같습니다. #include using namespace std; void draw(int n) //선을 그려주는 함수 { for(int i=0;i